A Hybrid Multi-objective Genetic Algorithm for Bi-objective Time Window Assignment Vehicle Routing Problem
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.
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.
Copyright (c) 2019 Manman Li, Jian Lu, Wenxin Ma
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).