The dynamic multiperiod vehicle routing problem with probabilistic information. (English) Zbl 1348.90059
Summary: This paper introduces the Dynamic Multiperiod Vehicle Routing Problem with Probabilistic Information, an extension of the Dynamic Multiperiod Vehicle Routing Problem in which, at each time period, the set of customers requiring a service in later time periods is unknown, but its probability distribution is available. Requests for service must be satisfied within a given time window that comprises several time periods of the planning horizon. We propose an adaptive service policy that aims at estimating the best time period to serve each request within its associated time window in order to reduce distribution costs. The effectiveness of this policy is compared with that of two alternative basic policies through a series of computational experiments.
References:
| [1] | Angelelli, E.; Speranza, M. G.; Salvelsbergh, M. W.P., Competitive analysis for dynamic multiperiod uncapacitated routing problems, Networks, 49, 308-317 (2007) · Zbl 1141.90334 |
| [2] | Archetti, C.; Hertz, A.; Speranza, M. G., Metaheuristics for the team orienteering problem, J Heuristics, 13, 49-76 (2007) |
| [3] | Archetti, C.; Feillet, D.; Hertz, A.; Speranza, M. G., The capacitated team orienteering and profitable tour problems, J Oper Res Soc, 60, 831-842 (2009) · Zbl 1171.90344 |
| [4] | Archetti, C.; Bianchessi, N.; Speranza, M. G., Optimal solutions for routing problems with profits, Discret Appl Math, 161, 547-557 (2013) · Zbl 1260.90156 |
| [5] | Baldacci, R.; Hadjiconstantinou, E.; Mingozzi, A., An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Oper Res, 52, 723-738 (2004) · Zbl 1165.90353 |
| [6] | Berbeglia, G.; Cordeau, J.-F.; Laporte, G., Dynamic pickup and delivery problems, Eur J Oper Res, 202, 8-15 (2010) · Zbl 1176.90048 |
| [7] | Bertsimas, D. J.; Van Ryzin, G. J., A stochastic and dynamic vehicle routing problem in the euclidean plane, Oper Res, 39, 601-615 (1991) · Zbl 0736.90027 |
| [8] | Feillet, D.; Dejax, P.; Gendreau, M., Travelling salesman problems with profits, Transp Sci, 39, 188-205 (2005) |
| [9] | Francis, P. M.; Smilowitz, K. R.; Tzur, M., The period vehicle routing problem and its extensions, (Golden, B. L.; Raghavan, S.; Wasil, E. A., The vehicle routing problem: latest advances and new challenges, operations research/computer science interfaces, vol. 43 (2008), Springer: Springer New York), 73-102 · Zbl 1187.90049 |
| [10] | Ghiani, G.; Manni, E.; Thomas, B. W., A comparison of anticipatory algorithms for the dynamic and stochastic traveling salesman problem, Transp Sci, 46, 374-387 (2012) |
| [11] | Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Res Logist, 34, 307-318 (1987) · Zbl 0647.90099 |
| [12] | Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Exploiting knowledge about future demands for real-time vehicle dispatching, Transp Sci, 40, 211-225 (2006) |
| [13] | Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Planned route optimization for real-time vehicle routing, (Zeimpekis, V.; Tarantilis, C. D.; Giaglis, G. M.; Minis, I., Dynamic fleet management (2007), Springer: Springer New York), 1-18 |
| [14] | Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of traveling salesman problems, J ACM, 7, 326-329 (1960) · Zbl 0100.15101 |
| [15] | Moretti Branchini, R.; Armentano, V. A.; Løkketangen, A., Adaptive granular local search heuristic for a dynamic vehicle routing problem, Comput Oper Res, 36, 2955-2968 (2009) · Zbl 1162.90349 |
| [16] | Papastavrou, J. D., A stochastic and dynamic routing policy using branching processes with state dependent immigration, Eur J Oper Res, 95, 167-177 (1996) · Zbl 0953.90502 |
| [17] | Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L., A review of dynamic vehicle routing problems, Eur J Oper Res, 225, 1-11 (2013) · Zbl 1292.90203 |
| [18] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 254-265 (1987) · Zbl 0625.90047 |
| [19] | Wen, M.; Cordeau, J.-F.; Laporte, G., The dynamic multi-period vehicle routing problem, Comput Oper Res, 37, 1615-1623 (2010) · Zbl 1189.90039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
