Username   Password       Forgot your password?  Forgot your username? 


Solving Dynamic Vehicle Routing Problem using Enhanced Genetic Algorithm with Penalty Factors

Volume 14, Number 4, April 2018, pp. 611-620
DOI: 10.23940/ijpe.18.04.p3.611620

Haitao Xu, Feng Duan, and Pan Pu

School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou, 310018, China

(Submitted on January 8, 2018; Revised on February 13, 2018; Accepted on March 22, 2018)


The vehicle routing problem (VRP) has become one of the focus issues in operations research and management sciences over the past two decades. One of its principal branches is the dynamic vehicle routing problem (DVRP), which can receive new order requests during the service process and make a timely response, unlike static vehicle routing problems (SVRP) where all information is known before the optimization starts. In this paper, we solve DVRP while using an enhanced genetic algorithm (GA) that tries to increase both diversity and global searching ability. The maximum saving method and the nearest neighbor method are adopted in the crossover operation to improve the path selection. Considering the near distance priority service principle (NDPSP) in the actual operation, a new assessment scheme with penalty factors is applied to our individual assessment. In addition, a paired-t test as a non-parametric statistical analysis is implemented to demonstrate the efficiency of the enhanced genetic optimization algorithm, based on a publicly available VRP benchmark, which includes 21 data sets. Analysis results show that our approach outperformed the published approached based on optimizing results.


References: 26

    1. A. M. F. M. Abdallah, D. L. Essam, and R. A. Sarker, “On Solving Periodic re-Optimization Dynamic Vehicle Routing Problems,” Applied Soft Computing, vol. 55, no. 1, pp.1-12, June 2017.
    2. D. Bhandari, N. R. Pal, and S. K. Pal, “Directed Mutation in Genetic Algorithms,” Information Sciences, vol. 79, no. 3-4, pp.251-270, July 1994.
    3. D. Cattaruzza, N. Absi, D. Feillet, and J. González-Feliu, “Vehicle Routing Problems for City Logistics,” Euro Journal on Transportation & Logistics, vol. 6, no. 1, pp.51-79, April 2017.
    4. Z. L. Chen and H. Xu, “Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows,” Transportation Science, vol. 40, no. 1, pp.74-88, February 2006.
    5. N. Christofides and J. E. Beasley, “The Period Routing Problem,” Networks, vol. 14, no. 2, pp.237-256, October 2006.
    6. F. Cruz, A. Subramanian, B. P. Bruck, and M. Iori, “A Heuristic Algorithm for a Single Vehicle Static Bike Sharing Rebalancing Problem,” Computers & Operations Research, vol. 79, no. 9, pp.19-33, March 2017.
    7. G. B. Dantzig, and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, vol. 6, no. 1, pp.80-91, October 1959.
    8. K. Deep and H. Mebrahtu, “Variant of Partially Mapped Crossover for the Travelling Salesman problems,” International Journal of Combinatorial Optimization Problems & Informatics, vol. 3, no. 1, pp.47-69, January 2012.
    9. M. Fisher, “Chapter 1 Vehicle Routing,” Handbooks in Operations Research & Management Science, vol. 8, no. 5, pp.1-33, 1995.
    10. F. T. Hanshar, and B. M. Ombuki-Berman, “Dynamic Vehicle Routing using Genetic Algorithms,” Applied Intelligence, vol. 27, no. 1, pp.89-99, June 2007.
    11. W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, “A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem,” Engineering Applications of Artificial Intelligence, vol. 21, no. 4, pp.548-557, June 2008.
    12. G. Kim, Y. S. Ong, T. Cheong, and P. S. Tan, "Solving the Dynamic Vehicle Routing Problem Under Traffic Congestion,” IEEE Transactions On Intelligent Transportation Systems, vol. 17, no. 8, pp.2367-2380, August 2016.
    13. S. Kritzinger, K. Doerner, F. Tricoire, and R. Hartl, “Adaptive Search Techniques for Problems in Vehicle Routing, Part I: A Survey,” Yugoslav Journal of Operations Research, vol. 25, no. 1, pp.3-31, 2015.
    14. J. L. Liu and Z. J. Ma, “Multi-depot Open Vehicle Routing Problem with Time Windows based on Vehicle Leasing and Sharing,” Systems Engineering-Theory & Practice, vol. 33, no. 3, pp.666-675, March 2013.
    15. R. Montemanni, L. M. Gambardella, A. E. Rizzoli, and A. V. Donati, “Ant Colony System for a Dynamic Vehicle Routing Problem,” Journal of Combinatorial Optimization, vol. 10, no. 4, pp.327-343, December 2005.
    16. T. Ning, C. Guo, R. Chen, and H. Jin, “A Novel Hybrid Method on VRP with Pickup and Delivery,” Open Cybernetics & Systemics Journal, vol. 10, no. 1, pp.56-60, April 2016.
    17. H. M. Nuñez, and H. Önal, “An Economic Analysis of Transportation Fuel Policies in Brazil: Fuel Choice, Land Use, and Environmental Impacts,” Energy Economics, vol. 55, no. 2, pp.319-331, March 2016.
    18. B. Ombuki, B. J. Ross, and F. Hanshar. “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows,” Applied Intelligence, vol. 24, no. 1, pp.17-30, February 2006.
    19. D. Sabolić, “Introduction to Genetic Algorithm,” Artificial Life, vol. 3, no. 1, pp.63-65, 2014.
    20. É. Taillard, “Parallel Iterative Search Methods for Vehicle Routing Problems,” Networks, vol. 23, no. 8, pp.661-673, December 1993.
    21. T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei, “A Hybrid Genetic Algorithm for Multi-depot and Periodic Vehicle Routing Problems,” Operations Research, vol. 60, no. 3, pp.611-624, January 2012.
    22. S. Vonolfen and M. Affenzeller, “Distribution of Waiting Time for Dynamic Pickup and Delivery Problems,” Annals of Operations Research, vol. 236, no. 2, pp.359-382, DATE, January 2016.
    23. Y. Wang, X. Ma, and Z. Li et al., “Profit Distribution in Collaborative Multiple Centers Vehicle Routing Problem,” Journal of Cleaner Production, vol. 144, no. 1, pp.203-219, February 2017.
    24. H. Xie and M. Zhang, “Parent Selection Pressure Auto-Tuning for Tournament Selection in Genetic Programming,” IEEE Transactions On Evolutionary Computation, vol. 17, no. 1, pp.1-19, February 2013.
    25. W. U. Yanlian, H. Jiang, J. Zhuang, X. Guo, and X. U. Yihua, “Research of Individual Advantages Genetic Algorithm based on Elitist Strategy,” Computer Engineering & Applications, vol. 52, no. 7, pp.143-149, 2016.
    26. L. Z. Zhang, S. Y. Chen, and Y. Y. Cui, “Genetic Algorithm Optimization in Vehicle Routing Problem,” Applied Mechanics & Materials, vols. 361-363, pp.2249-2254, August 2013.


      Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

      Download this file (IJPE-2018-04-03.pdf)IJPE-2018-04-03.pdf[Solving Dynamic Vehicle Routing Problem using Enhanced Genetic Algorithm with Penalty Factors]563 Kb
      This site uses encryption for transmitting your passwords.