The selective full truckload multi-depot vehicle routing problem with time windows: Formulation and a genetic algorithm

Document Type : Research Paper

Author

Information Technology and Management, ENSIAS - Mohammed V University, Rabat, Morocco

Abstract

The process of an empty backhaul truck returning to its home domicile after a regular delivery journey has attracted many logistics companies in the modern world economy. This paper studies a selective full truckload multi-depot vehicle routing problem with time windows (SFTMDVRPTW) in an empty return scenario. This problem aims at planning a set of backhaul routes for a fleet of trucks that serve a subset of selected transportation demands from a number of full truckload orders to maximize the overall profit, given constraints of availability and time windows. After reviewing the literature related to full truckload vehicle routing problems, based on the professional characteristics encountered as well as on the resolution approaches used, we formulate a mixed-integer linear programming (MILP) model for the SFTMDVRPTW. Since the problem is NP-hard, we propose a genetic algorithm (GA) to yield a near-optimal solution. A new two-part chromosome is used to represent the solution to our problem. Through a selection grounded on the elitist and roulette method, a new crossover operator called “selected two-part crossover chromosome (S-TCX)” and an exchange mutation operator, new individuals are generated. The proposed MILP model and GA are evaluated on newly randomly generated instances. The findings prove that the GA significantly outperforms the CPLEX solver in solution quality and CPU time.

Keywords

References

Aras N., Aksen D. and Tuǧrul Tekin M. (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C: Emerging Technologies, Vol. 19(5), pp. 866-884.
Arunapuram S., Mathur K. and Solow D. (2003). Vehicle Routing and Scheduling with Full Truckloads. Transportation Science, Vol. 37(2), pp. 170-182.
Ávila T., Corberán Á., Plana I. and Sanchis J. M. (2017). Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem. EURO Journal on Computational Optimization, Vol. 5(3), pp. 339-365.
Ball M. O., Golden B. L., Assad A. A. and Bodin L. D. (1983). Planning for truck fleet size in the presence of a common-carrier option. Decision Sciences, Vol. 14(1), pp. 103-120.
Baker B. M. and Ayechew M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, Vol. 30(5), pp. 787-800.
Braekers K., Caris A. and Janssens G. K. (2013). Integrated planning of loaded and empty container movements. OR Spectrum, Vol. 35(2), pp. 457-478.
Braekers K., Caris A. and Janssens G. K. (2014). Bi-objective optimization of drayage operations in the service area of intermodal terminals. Transportation Research Part E: Logistics and Transportation Review, Vol. 65(1), pp. 50-69.
Berger J. and Barkaoui M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & operations research, Vol. 31(12), pp. 2037-2053.
Bettinelli A., Ceselli A. and Righini G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies,Vol. 19(5), pp. 723-740.
Bolaños R. I., Escobar J. W. and Echeverri M. G. (2018). A metaheuristic algorithm for the multi-depot vehicle routing problem with heterogeneous fleet. International Journal of Industrial Engineering Computations, Vol. 9(4), pp. 461–478.
Bouziyane B., Dkhissi B. and cherkaoui M. (2018). Solving a dynamic vehicle routing problem with soft time windows based on static problem resolution by a hybrid approach. International Journal f Supply and Operations Management, Vol. 5(2), pp. 134-151.
Caris A. and Janssens G. K. (2009). A local search heuristic for the pre-and end-haulage of intermodal container terminals. Computers and Operations Research, Vol. 36(10), pp. 2763-2772.
Carter A.E. and Ragsdale C.T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, Vol.175 (1), pp. 246–257.
Cordeau J.-F., Laporte G. and Mercier A. (2004). An improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. Journal of the Operational Research Society, Vol. 55, pp. 542-546.
Currie R. H. and Salhi S. (2003). Exact and heuristic methods for a full-load, multi-terminal, vehicle scheduling problem with backhauling and time windows. Journal of the Operational Research Society, Vol. 54(4), pp. 390-400.
Currie R. H. and Salhi S. (2004). A tabu search heuristic for a full-load, multi-terminal, vehicle scheduling problem with backhauling and time windows. Journal of Mathematical Modelling and Algorithms, Vol. 3(3), pp. 225-243.
Desrosiers J., Laporte G., Sauve M., Soumis F. and Taillefer S. (1988). Vehicle routing with full loads. Computers and Operations Research, Vol 15(3), pp. 219-226.
Dimitriou L. (2021). Optimal competitive pricing in European port container terminals: A game-theoretical framework. Transportation Research Interdisciplinary Perspectives, Vol. 9, pp. 1–12.
EL Bouyahyiouy K. and Bellabdaoui A. (2016). A new crossover to solve the full truckload vehicle routing problem using genetic algorithm. 3rd International Conference on Logistics Operations Management (GOL), 7731675, pp. 1–6.
EL Bouyahyiouy K. and Bellabdaoui A. (2017). An ant colony optimization algorithm for solving the full truckload vehicle routing problem with profit. International Colloquium on Logistics and Supply Chain Management: Competitiveness and Innovation in Automobile and Aeronautics Industries (LOGISTIQUA),7962888, pp. 142-147.
Goldberg D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley Longman, Boston, MA.
Golden B. L. and Wong R. T. (1981). Capacitated arc routing problems. Networks, Vol. 11(3), pp. 305-315.
Grimault A., Bostel N. and Lehuédé F. (2017). An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization. Computers and Operations Research, Vol. 88, pp. 1-14.
Gronalt M., Hartl R. F. and Reimann M. (2003). New savings based algorithms for time constrained pickup and delivery of full truckloads. European Journal of Operational Research, Vol. 151(3), pp. 520-535.
Gronalt M. and Hirsch P. (2007). Log-truck scheduling with a tabu search strategy.Operations Research/ Computer Science Interfaces Series,Vol. 39, pp. 65-88.
Holland J. H. (1975). Adaptation in natural and artificial systems, Ann Arbor, MI: University of Michigan Press
Ho W., Ho G. T., Ji P. and Lau H. C (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, Vol. 21(4), pp. 548-557.
Imai A., Nishimura E. and Current J. (2007). A Lagrangian relaxation-based heuristic for the vehicle routing with full container load. European Journal of Operational Research, Vol. 176(1), pp. 87-105.
Jula H., Dessouky M., Ioannou P. and Chassiakos A. (2005). Container movement by trucks in metropolitan networks: Modeling and optimization. Transportation Research Part E: Logistics and Transportation Review, Vol. 41(3), pp. 235-259.
Lahyani R., Gouguenheim A. -L. and Coelho L. C. (2019). A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems. International Journal of Production Research, Vol. 57(22), pp. 6963-6976.
Lahyani R., Khemakhem M. and Semet F. (2017). A unified matheuristic for solving multi-constrained traveling salesman problems with profits. EURO Journal on Computational Optimization, Vol. 5(3), pp. 393-422.
Lenstra J. K. and Rinnooy-Kan A. H. G. (1981). Complexity of Vehicle Routing and Scheduling Problems. Networks, vol. 11(2), pp. 221- 227.
Liu R., Jiang Z., Fung R. Y. K., Chen F. and Liu X. (2010a). Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration. Computers and Operations Research, Vol. 37(5), pp. 950-959.
Liu R., Jiang Z., Liu X. and Chen F. (2010b). Task selection and routing problems in collaborative truckload transportation. Transportation Research Part E: Logistics and Transportation Review, Vol. 46(6), pp. 1071-1085.
Lysgaard J., Letchford A. N. and Eglese R. W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, Vol. 100(2), pp. 423-445.
Mirabi M., Shokri N. and Sadeghieh A. (2016). Modeling and Solving the Multi-depot Vehicle Routing Problem with Time Window by Considering the Flexible End Depot in Each Route. International Journal of Supply and Operations Management, Vol. 3(3), pp. 1373-1390.
Nossack J. and Pesch E. (2013). A truck scheduling problem arising in intermodal container transportation. European Journal of Operational Research, Vol. 230(3), pp. 666-680.
Powell W. B., Sheffi Y., Nickerson K. S., Butterbaugh K. and Atherton S. (1988). Maximizing profits for North American van lines’ truckload division: A new framework for pricing and operations. Interfaces, Vol. 18 (1), pp. 21-41.
Rincon-Garcia N., Waterson B. J and Cherrett T. J. (2017). A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows. International Journal of Industrial Engineering Computations, Vol. 8(1), pp. 141–160.
Solomon M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, Vol. 35(2), pp. 254-265.
Uchoa E., Pecin D., Pessoa A., Poggi M., Vidal T. and Subramanian A. (2017). New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, Vol. 257(3), pp. 845-858.
Venkateshan P. and Mathur K. (2011). An efficient column-generation-based algorithm for solving a pickup-and-delivery problem. Computers and Operations Research, Vol. 38(12), pp. 1647-1655.
Wang X. and Regan A. C. (2002). Local truckload pickup and delivery with hard time window constraints. Transportation Research Part B: Methodological, Vol. 36(2), pp. 97-112.
Xue N., Bai R., Qu R. and Aickelin U. (2021). A hybrid pricing and cutting approach for the multi-shift full truckload vehicle routing problem. European Journal of Operational Research, Vol. 292(2), pp. 500-514.
Yuan S., Skinner B., Huang S. and Liu D. (2013). A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research, Vol. 228(1), pp. 72-82.
Yu B., Yang Z. Z. andYao B. Z. (2011). A hybrid algorithm for vehicle routing problem with time windows. Expert Systems with Applications, Vol. 38(1), pp. 435-441.
Zhang R., Yun W. Y. and Moon I. (2009). A reactive tabu search algorithm for the multi-depot container truck transportation problem. Transportation Research Part E: Logistics and Transportation Review, Vol. 45(6), pp. 904-914.
Zhang R., Yun W. Y. and Kopfer H. (2010). Heuristic-based truck scheduling for inland container transportation. OR Spectrum, Vol. 32(3), pp. 787-808.
Zolfagharinia H. and Haughton M. (2016). Effective truckload dispatch decision methods with incomplete advance load information European Journal of Operational Research, Vol. 252(1), pp. 103-121.
International Journal of Supply and Operations Management
Volume 9, Issue 3
August 2022
Pages 299-320

Files

Share

How to cite

Statistics