A generalized multi-depot vehicle routing problem with replenishment based on LocalSolver

Abstract: In this paper, we consider the multi depot heterogeneous vehicle routing problem with time windows in which vehicles may be replenished along their trips. Using the modeling technique in a new-generation solver, we construct a novel formulation considering a rich series of constraint conditions and objective functions. Computation results are tested on an example comes from the real-world application and some cases obtained from the benchmark problems. The results show the good performance of local search method in the efficiency of replenishment system and generalization ability. The variants can be used to almost all kinds of vehicle routing problems, without much modification, demonstrating its possibility of practical use.

How to cite this paper

 Zhang, Y., Qi, M., Miao, L & Wu, G. (2015). A generalized multi-depot vehicle routing problem with replenishment based on LocalSolver.International Journal of Industrial Engineering Computations , 6(1), 81-98.

Refrences

Angelelli, E., & Grazia Speranza, M. (2002). The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 137(2), 233-247.

Azi, N., Gendreau, M., & Potvin, J. Y. (2012). A dynamic vehicle routing problem with multiple delivery routes. Annals of Operations Research, 199(1), 103-112.

Azi, N., Gendreau, M., & Potvin, J. Y. (2010). An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202(3), 756-763.

Azi, N., Gendreau, M., & Potvin, J. Y. (2007). An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European journal of operational research, 178(3), 755-766.

Battarra, M., Monaci, M., & Vigo, D. (2009). An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Computers & Operations Research, 36(11), 3041-3050.

Benjamin, A. M., & Beasley, J. E. (2010). Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Computers & Operations Research, 37(12), 2270-2280.

Benoist, T., Estellon, B., Gardi, F., Megel, R., & Nouioua, K. (2011). Localsolver 1. x: a black-box local-search solver for 0-1 programming. 4OR, 9(3), 299-316.

Brandao, J. C. S., & Mercer, A. (1998). The multi-trip vehicle routing problem. Journal of the Operational research society, 799-805.

Brand?o, J., & Mercer, A. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European journal of operational research, 100(1), 180-191.

Br?ysy, O., & Gendreau, M. (2005a). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation science, 39(1), 104-118.

Br?ysy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation science, 39(1), 119-139.

Buhrkal, K., Larsen, A., & Ropke, S. (2012). The waste collection vehicle routing problem with time windows in a city logistics context. Procedia-Social and Behavioral Sciences, 39, 241-254.

Cattaruzza, D., Absi, N., Feillet, D., & Vidal, T. (2014). A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Research, 236(3), 833-848.

Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2), 105-119.

Crevier, B., Cordeau, J. F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756-773.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.

Fleischmann, B. (1990). The vehicle routing problem with multiple use of the vehicles. Working Paper, Fachbereich Wirtschaftswissenschaften, Universit?t Hamburg, Germany.

Guerrero, W. J., Prodhon, C., Velasco, N., & Amaya, C. A. (2013). Hybrid heuristic for the inventory location-routing problem with deterministic demand. International Journal of Production Economics, 146(1), 359-370.

Gulczynski, D., Golden, B., & Wasil, E. (2011). The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 61(3), 794-804.

Jordan, W. C. (1987). Truck backhauling on networks with many terminals. Transportation Research Part B: Methodological, 21(3), 183-193.

Jordan, W. C., & Burns, L. D. (1984). Truck backhauling on two terminal networks. Transportation Research Part B: Methodological, 18(6), 487-503.

Kim, B. I., Kim, S., & Sahoo, S. (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research, 33(12), 3624-3642.

Kuo, Y., & Wang, C. C. (2012). A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, 39(8), 6949-6954.

Lin, C. K. Y., & Kwok, R. C. W. (2006). Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. European Journal of Operational Research, 175(3), 1833-1849.

Mingozzi, A., Roberti, R., & Toth, P. (2013). An exact algorithm for the multitrip vehicle routing problem. INFORMS Journal on Computing, 25(2), 193-207.

Olivera, A., & Viera, O. (2007). Adaptive memory programming for the vehicle routing problem with multiple trips. Computers & Operations Research, 34(1), 28-47.

Ombuki-Berman, B. M., Runka, A., & Hanshar, F. (2007, May). Waste collection vehicle routing problem with time windows using multi-objective genetic algorithms. In Proceedings of the Third IASTED International Conference on Computational Intelligence (pp. 91-97). ACTA Press.

Petch, R. J., & Salhi, S. (2003). A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Applied Mathematics, 133(1), 69-92.

Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34(8), 2403-2435.

Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4), 455-472.

Salhi, S., & Petch, R. J. (2007). A GA based heuristic for the vehicle routing problem with multiple trips. Journal of Mathematical Modelling and Algorithms, 6(4), 591-613.

Sevilla, F. C., & de Blas, C. S. (2003). Vehicle routing problem with time windows and intermediate facilities. SEIO ?03 Edicions de la Universitat de Lleida, 3088-3096.

Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.

Taillard, E. D., Laporte, G., & Gendreau, M. (1996). Vehicle routeing with multiple use of vehicles. Journal of the Operational research society, 1065-1070.

Toth, P., & Vigo, D. (Eds.). (2001). The vehicle routing problem. Siam.

Tung, D. V., & Pinnoi, A. (2000). Vehicle routing–scheduling for waste collection in Hanoi. European Journal of Operational Research, 125(3), 449-468.

Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.

Xu, Y., Wang, L., & Yang, Y. (2012). A New Variable Neighborhood Search Algorithm for the Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows. Electronic Notes in Discrete Mathematics, 39, 289-296.