The electric fleet size and mix vehicle routing problem with time windows and recharging stations. (English) Zbl 1346.90126
Summary: Due to new regulations and further technological progress in the field of electric vehicles, the research community faces the new challenge of incorporating the electric energy based restrictions into vehicle routing problems. One of these restrictions is the limited battery capacity which makes detours to recharging stations necessary, thus requiring efficient tour planning mechanisms in order to sustain the competitiveness of electric vehicles compared to conventional vehicles. We introduce the Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations (E-FSMFTW) to model decisions to be made with regards to fleet composition and the actual vehicle routes including the choice of recharging times and locations. The available vehicle types differ in their transport capacity, battery size and acquisition cost. Furthermore, we consider time windows at customer locations, which is a common and important constraint in real-world routing and planning problems. We solve this problem by means of branch-and-price as well as proposing a hybrid heuristic, which combines an Adaptive Large Neighbourhood Search with an embedded local search and labeling procedure for intensification. By solving a newly created set of benchmark instances for the E-FSMFTW and the existing single vehicle type benchmark using an exact method as well, we show the effectiveness of the proposed approach.
Software:
VRPReferences:
| [2] | Baldacci, R.; Bartolini, E.; Mingozzi, A.; Roberti, R., An exact solution framework for a broad class of vehicle routing problems, Computational Management Science, 7, 3, 229-268 (2010) · Zbl 1194.90011 |
| [3] | Baldacci, R.; Battarra, M.; Vigo, D., Routing a heterogeneous fleet of vehicles, (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges. The vehicle routing problem: Latest advances and new challenges, Operations Research/Computer Science Interfaces, Vol. 43 (2008), Springer: Springer US), 3-27 · Zbl 1187.90038 |
| [4] | Bektas, T.; Laporte, G., The pollution-routing problem, Transportation Research Part B: Methodological, 45, 1232-1250 (2011) |
| [5] | Bräysy, O.; Dullaert, W.; Hasle, G.; Mester, D. I.; Gendreau, M., An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows, Transportation Science, 42, 3, 371-386 (2008) |
| [6] | Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part i: Route construction and local search algorithms, Transportation Science, 39, 1, 104-118 (2005) |
| [7] | Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part ii: Metaheuristics, Transportation Science, 39, 1, 119-139 (2005) |
| [8] | Bräysy, O.; Porkka, P.; Dullaert, W.; Repoussis, P. P.; Tarantilis, C. D., A well-scaleable metaheuristic for the fleet size and mix vehicle routing problem with time windows, Expert Systems with Applications, 36, 4, 8460-8475 (2008) |
| [9] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581 (1964) |
| [10] | Conrad, R. G.; Figliozzi, M. A., The recharging vehicle routing problem, (Doolen, T.; Aken, E. V., Proceedings of the 2011 industrial engineering research conference (2011), Reno: Reno Nevada) |
| [11] | Cordeau, J.-F; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 8, 928-936 (2001) · Zbl 1181.90034 |
| [12] | Crevier, B.; Cordeau, J. F.; Laporte, G., The multi-depot vehicle routing problem with inter-depot routes, European Journal of Operational Research, 176, 2, 756-773 (2007) · Zbl 1103.90032 |
| [13] | Dekker, R.; Bloemhof, J.; Mallidis, I., Operations research for green logistics - an overview of aspects, issues, contributions and challenges, European Journal of Operational Research, 219, 3, 671-679 (2012) |
| [14] | Dell’Amico, M.; Monaci, M.; Pagani, C.; Vigo, D., Heuristic approaches for the fleet size and mix vehicle routing problem with time windows, Transportation Science, 41, 4, 516-526 (2007) |
| [15] | Desaulniers, G.; Fausto, E.; Irnich, S.; Schneider, M., Technical report les cahiers du gerad, g-2014-110 (2014), Montral: Montral Canada |
| [16] | Desaulniers, G.; Lessard, F.; Hadjar, A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transportation Science, 42, 3, 387-404 (2008) |
| [17] | Desrosiers, J.; Lübbecke, M., Branch-price-and-cut algorithms, Wiley encyclopedia of operations research and management science (EORMS) (2011), Wiley |
| [18] | Di Gaspero, L.; Schaerf, A., Multi-neighbourhood local search with application to course timetabling, (Burke, E.; De Causmaecker, P., Practice and theory of automated timetabling IV (2002), Springer, DE), 262-275 |
| [19] | Dullaert, W.; Janssens, G. K.; Sörensen, K.; Vernimmen, B., New heuristics for the fleet size and mix vehicle routing problem with time windows, Journal of the Operations Research Society, 53, 11, 1232-1238 (2002) · Zbl 1139.90336 |
| [20] | Erdoǧan, S.; Miller-Hooks, E., A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 48, 1, 100-114 (2012) |
| [21] | Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014 |
| [22] | Goeke, D.; Schneider, M., Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, 245, 1, 81-99 (2015) · Zbl 1346.90115 |
| [23] | Golden, B.; Assad, A.; Levy, L.; Gheysens, F., The fleet size and mix vehicle routing problem, Computers & Operations Research, 11, 1, 49-66 (1984) · Zbl 0607.90043 |
| [24] | Hart, J. P.; Shogan, A. W., Semi-greedy heuristics: an empirical study, Operations Research Letters, 6, 3, 107-114 (1987) · Zbl 0615.90082 |
| [25] | Hiermann, G.; Prandtstetter, M.; Rendl, A.; Puchinger, J.; Raidl, G. R., Metaheuristics for solving a multimodal home-healthcare scheduling problem, Central European Journal of Operations Research, 23, 1, 89-113 (2015) · Zbl 1339.90140 |
| [26] | Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation (2005), Springer), 33-65 · Zbl 1130.90315 |
| [27] | Irnich, S.; Villeneuve, D., The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3, INFORMS Journal on Computing, 18, 3, 391-406 (2006) · Zbl 1241.90161 |
| [28] | Kindervater, G. A.P.; Savelsbergh, M. W.P., Vehicle routing: Handling edge exchanges, (Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), John Wiley & Sons Ltd), 337-360 · Zbl 0887.90060 |
| [29] | Koç, Ç.; Bektas, T.; Jabali, O., Laporte g the fleet size and mix pollution-routing problem, Transportation Research Part B: Methodological, 70, 230-254 (2014) |
| [30] | Liu, F. H.; Shen, S. Y., The fleet size and mix vehicle routing problem with time windows, The Journal of the Operational Research Society, 50, 7, 721-732 (1999) · Zbl 1054.90522 |
| [31] | Nagata, Y.; Bräysy, O.; Dullaert, W., A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 37, 4, 724-737 (2010) · Zbl 1175.90046 |
| [32] | Paraskevopoulos, D. C.; Repoussis, P. P.; Tarantilis, C. D.; Ioannou, G.; Prastacos, G. P., A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows, Journal of Heuristics, 14, 5, 425-455 (2008) · Zbl 1211.90313 |
| [33] | Pelletier, S.; Jabali, O.; Laporte, G., Goods distribution with electric vehicles: review and research perspectives, Technical Report CIRRELT-2014-44, CIRRELT, Montreal, Canada (2015) |
| [34] | Pisinger, D.; Ropke, S., Large neighborhood search, (Gendreau, M.; Potvin, J. Y., Handbook of metaheuristics, international series in operations research & management science, Vol. 146 (2010), Springer: Springer US), 399-419 · Zbl 1198.90002 |
| [35] | Potvin, J. Y.; Rousseau, J. M., A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European Journal of Operational Research, 66, 3, 331-340 (1993) · Zbl 0775.90154 |
| [36] | Repoussis, P. P.; Tarantilis, C. D., Solving the fleet size and mix vehicle routing problem with time windows via adaptive memory programming, Transportation Research Part C: Emerging Technologies, 18, 5, 695-712 (2010) |
| [37] | Righini, G.; Salani, M., Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization, 3, 3, 255-273 (2006) · Zbl 1149.90167 |
| [38] | Ropke, S.; Cordeau, J. F., Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 3, 267-286 (2009) |
| [39] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472 (2006) |
| [40] | Sbihi, A.; Eglese, R. W., Combinatorial optimization and green logistics, Annals of Operations Research, 175, 1, 159-175 (2010) · Zbl 1185.90178 |
| [41] | Schneider, M.; Sand, B.; Stenger, A., A note on the time travel approach for handling time windows in vehicle routing problems, Computers & Operations Research, 40, 10, 2564-2568 (2013) · Zbl 1348.90126 |
| [42] | Schneider, M.; Stenger, A.; Goeke, D., The electric vehicle routing problem with time windows and recharging stations, Transportation Science, 48, 4, 500-520 (2014) |
| [43] | Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Maher, M. J.; Puget, J. F., Proceedings of the 4th international conference on principles and practice of constraint programming. CP ’98 (1998), Springer: Springer UK), 417-431 |
| [44] | Tarantilis, C. D.; Zachariadis, E. E.; Kiranoudis, C. T., A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities, INFORMS Journal on Computing, 20, 1, 154-168 (2008) · Zbl 1243.90027 |
| [45] | Toth, P.; Vigo, D., Vehicle routing: problems, methods, and applications, MOS-SIAM Series on Optimization (2014), SIAM: SIAM Philadelphia, PA · Zbl 1305.90012 |
| [46] | Trick, M. A., A linear relaxation heuristic for the generalized assignment problem, Naval Research Logistics (NRL), 39, 2, 137-151 (1992) · Zbl 0758.90047 |
| [47] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Heuristics for multi-attribute vehicle routing problems: a survey and synthesis, European Journal of Operational Research, 231, 1, 1-21 (2013) · Zbl 1317.90006 |
| [48] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 40, 1, 475-489 (2013) · Zbl 1349.90137 |
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.
