首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A memetic algorithm for the multiperiod vehicle routing problem with profit
Authors:Zizhen Zhang  Oscar Che  Brenda Cheang  Andrew Lim  Hu Qin
Institution:1. Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon Tong, Kowloon, Hong Kong;2. Division of Information and Technology Studies, Faculty of Education, The University of Hong Kong, Pokfulam, Hong Kong;3. School of Management, Huazhong University of Science and Technology, Wuhan, China
Abstract:In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.
Keywords:Memetic algorithm  Metaheuristics  Giant-tour  Multiperiod  Periodic vehicle routing
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号