基于时空聚类的带时间窗车辆路径规划算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (3): 218-222.

基于时空聚类的带时间窗车辆路径规划算法

戚铭尧,张金金,任丽

清华大学深圳研究生院物流与交通学部深圳518055;清华大学深圳研究生院物流与交通学部深圳518055;清华大学深圳研究生院物流与交通学部深圳518055

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金面上项目(71272030),深圳科技计划项目(CXZZ20130321145336439) ,东莞科技计划项目(201010810107)资助

Vehicle Routing Algorithm Based on Spatiotemporal Clustering

QI Ming-yao,ZHANG Jin-jin and REN Li

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解。以含1000个点的标准问题集作为算例,计算结果表明,与不采用时空聚类的方法相比,该算法能在更短的时间内取得更好的解,显示了在解决大规模车辆路径问题时具有很好的潜力。

关键词: 车辆路径问题,时间窗,时空距离,聚类分析,遗传算法,可变邻域搜索中图法分类号O22,TP31文献标识码A

Abstract: A route improvement method that considers spatial and temporal features simultaneously was proposed to solve vehicle routing problem with time windows．A spatiotemporal representation of vehicle routes was presented to measure the spatiotemporal distance between two customers．Then,a genetic algorithm was designed to cluster the customers into a few groups according to spatiotemporal distances．The resulting customer groups were then used for route adjustment:if a customer was moved to another route,only the nearby routes were searched and considered．By this means the search space is dramatically reduced．The calculation on 1000-customer examples designed by Gehring and Homberger shows that the proposed algorithm can get better solution in shorter time.

Key words: Vehicle routing problem,Time windows,Spatiotemporal distance,Clustering analysis,Genetic algorithm,Variable neighborhood search

戚铭尧,张金金,任丽. 基于时空聚类的带时间窗车辆路径规划算法[J]. 计算机科学, 2014, 41(3): 218-222. https://doi.org/

QI Ming-yao,ZHANG Jin-jin and REN Li. Vehicle Routing Algorithm Based on Spatiotemporal Clustering[J]. Computer Science, 2014, 41(3): 218-222. https://doi.org/

参考文献

[1] Dantzig G B,Ramser J H．The Truck Dispatching Problem [J]．Management Science,1959,6:80-91
[2] Laporte G．What you should know about the vehicle routingproblem [J]．Naval Research Logistics,2007,54:811-819
[3] Brysy O,Gendreau M．Vehicle Routing Problem,Part I:Route Construction and Local Search Algorithms [J]．Transportation Science,2005,39(1):104-118
[4] Brysy O,Gendreau M．Vehicle Routing Problem with TimeWindows,Part II:Metaheuristics [J]．Transportation Science,2005,39(1):119-139
[5] Gendreau M,Tarantilis C D．Solving large-scale vehicle routing problems with time windows:the state-of-the-art[R]．Technical report 2010-04．CIRRELT,Montreal,QC,Canada,2010
[6] Mladenovic N,Hansen P．Variable neighborhood search [J]．Computers and Operations Research,1997,24:1097-1100
[7] Ganesh K,Narendran T T．CLOVES:A Cluster-and-searchHeuristic to Solve the Vehicle Routing Problem with Delivery and Pick-up [J]．European Journal of Operational Research,2007,178(3):699-717
[8] Ostertag L,Doerner K F,Hart R F．A Variable Neighborhood Search Integrated in the POPMUSIC Framework for Solving Large Scale Vehicle Routing Problems[C]∥Proceedings of the 5th International Workshop on Hybrid Meta-heuristics,2008．Málaga,Spain,2008:29-42
[9] Vidal T,Crainic T G,Gendreau M,et al.A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows[J]．Computers & Operations Research,2013,40:475-489
[10] Hgerstrand T．What about people in regional science[C]∥Papers and proceedings of the regional science association．1970,24:7-21
[11] Kwan M P,Murray A T,O′Kelly,et al．Recent Advances in Accessibility Research:Representation,Methodology and Applications[J]．Journal of Geographical Systems,2003,5:129-138
[12] Lucasius C B,Dane A D,Kateman G．On K-medoid Clustering of Large Data Sets with the Aid of a Genetic Algorithm:Background,Feasibility and Comparison [J]．Analytica Chimica Acta,1993,282(3):647-669
[13] Solomon M．Algorithms for the vehicle routing and scheduling problems with time window constraints [J]．Operations Research,1987,35(2):254-265
[14] Gehring H,Homberger J．Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows [J]．Journal of Heuristics,2002,8(3):251-276

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed