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.

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.