A Hybrid Multi-objective Genetic Algorithm for Bi-objective Time Window Assignment Vehicle Routing Problem

  • Manman Li School of transport, Southeast university, China
  • Jian Lu Jiangsu Key Laboratory of Urban ITS, Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies and School of Transportation, Southeast University
  • Wenxin Ma
DOI: https://doi.org/10.7307/ptt.v31i5.3057
Keywords: vehicle routing, time window assignment, uncertain demand, time-dependent travel time, multi-objective genetic algorithms, local search

Abstract

Providing a satisfying delivery service is an important way to maintain the customers’ loyalty and further expand profits for manufacturers and logistics providers. Considering customers’ preferences for time windows, a bi-objective time window assignment vehicle routing problem has been introduced to maximize the total customers’ satisfaction level for assigned time windows and minimize the expected delivery cost. The paper designs a hybrid multi-objective genetic algorithm for the problem that incorporates modified stochastic nearest neighbour and insertion-based local search. Computational results show the positive effect of the hybridization and satisfactory performance of the metaheuristics. Moreover, the impacts of three characteristics are analysed including customer distribution, the number of preferred time windows per customer and customers’ preference type for time windows. Finally, one of its extended problems, the bi-objective time window assignment vehicle routing problem with time-dependent travel times has been primarily studied.

Author Biography

Manman Li, School of transport, Southeast university, China

Manman Li was born January 7, 1991 in Shaanxi, China. She completed her bachelor's degree and Master's degree at Dalian Maritime University  in Liaoning, China. She is now  a Ph.D. candidate at Southeast university in Jiangsu, China

References

Spliet R, Gabor AF. Time window assignment vehicle routing problem. Transportation Science. 2015;49(4): 721-731.

Spliet R, Desaulniers G. The discrete time window assignment vehicle routing problem. European Journal of Operational Research. 2015;(244): 379-391.

Li MM, Lu J, An Y. Bi-objective time window assignment vehicle routing problem considering customer preferences for time windows. Journal of Southeast University (Natural Science Edition). 2018;48(3): 568-575.

Agatz N, Campbell A, Savelsbergh M. Time slot management in attended home delivery. Transportation Science. 2011;45(3): 435-449.

Campbell AM, Savelsbergh M. Decision support for consumer direct grocery initiatives. Transportation Science. 2005;3(39): 313-327.

Ehmke JF, Campbell AM. Customer acceptance mechanism for home deliveries in metropolitan areas. European Journal of Operational Research. 2014;233: 193-207.

Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research. 2012;218: 1-6.

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

Bräysy O, Gendreau M. Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science. 2005;39(1): 119-139.

Pillac V, Gendreau M, Guéret C, et al. A review of dynamic vehicle routing problems. European Journal of Operational Research. 2013;225(1): 1-11.

Jozefowiez N, Semet F, Talbi EG. Multi-objective vehicle routing problems. European Journal of Operational Research. 2008;189: 293-309.

Huang Y, Zhao L, Woensel TV, et al. Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological. 2017;95: 169-195.

Pierre DM, Zakaria N. Stochastic partially optimized

cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows. Applied Soft Computing. 2017;52: 863-876.

Jung S, Haghani A. Genetic algorithm for the Time-Dependent vehicle routing problem. Transportation Research Record. 2001;1771: 164-171.

Bean JC. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing. 1994;6(2): 154-160.

Tan KC, Lee TH, Khor EF. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Transaction on Evolutionary Computation. 2001;5(6): 565-588.

Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation. 2002;6(2): 182-197.

Pradhananga R, Taniguchi E, Yamada T. Ant colony system based routing and scheduling for hazardous material transportation. Procedia – Social and Behavioral Sciences. 2010;2(3): 6097-6108.

Zitzler E, Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transaction on Evolutionary Computation. 1999;3(4): 257-271.

Schneider M, Stenger A, Goeke D. The electric vehicle-routing problem with time windows and recharging stations. Transportation Science. 2014;48(4): 500-520.

Ichoua S, Gendreau M, Potvin JY. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research. 2003;144: 379-396.

Published
2019-10-18
How to Cite
1.
Li M, Lu J, Ma W. A Hybrid Multi-objective Genetic Algorithm for Bi-objective Time Window Assignment Vehicle Routing Problem. Promet [Internet]. 2019Oct.18 [cited 2024Nov.24];31(5):513-25. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/3057
Issue
Vol 31 No 5 (2019)
Section
Articles

Copyright (c) 2019 Manman Li, Jian Lu, Wenxin Ma

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).