基于一种特设启发式算法的车辆优化调度问题研究
|
摘要
建立数学模型将最小车辆规模问题转化为车辆共享网络的精确表述,设计行程共享网络,通过结合了Edmond匹配算法,Dijkstra算法等经典算法的特设启发式算法解决共享网络的最大匹配和最优路径问题,进一步揭示车辆共享网络的结构特性,通过推导计算效率较高的优化车辆部署和调度算法以最优地解决最小车辆规模问题。用matlab仿真,得出最佳参数Δ,k的特设启发式算法,并进一步证明了该算法通过行程组合,减少了行程数量,进一步减少了车辆的需求,进而实现减少交通拥堵和环境污染的目标。
Establish mathematical models to translate the minimum vehicle size problem into an accurate representation of the vehicle's shared network. Design the itinerary sharing network, and combine the Edmond matching algorithm, the Dijkstra algorithm and other classical algorithms to solve the maximum matching and optimal path problem of the shared network, and further reveal the structural characteristics of the vehicle shared network. Optimize vehicle deployment and scheduling algorithms with higher computational efficiency to optimally address minimum vehicle size issues. Simulated with matlab, the special heuristic algorithm of the optimal parameters Δ, k is obtained, and it is further proved that the algorithm reduces the number of strokes through the stroke combination, further reduces the demand of the vehicle, and achieves the goal of reducing traffic congestion and environmental pollution.
Establish mathematical models to translate the minimum vehicle size problem into an accurate representation of the vehicle's shared network. Design the itinerary sharing network, and combine the Edmond matching algorithm, the Dijkstra algorithm and other classical algorithms to solve the maximum matching and optimal path problem of the shared network, and further reveal the structural characteristics of the vehicle shared network. Optimize vehicle deployment and scheduling algorithms with higher computational efficiency to optimally address minimum vehicle size issues. Simulated with matlab, the special heuristic algorithm of the optimal parameters Δ, k is obtained, and it is further proved that the algorithm reduces the number of strokes through the stroke combination, further reduces the demand of the vehicle, and achieves the goal of reducing traffic congestion and environmental pollution.
引文
[1] 戴冬,王江晴.一种基于禁忌搜索算法的车辆路径问题的改进算法[J].中南民族大学学报(自然科学版),2007,26(1):64-66.
[2] BAKER,BARRIE M,AYECHEW M A.A genetic algorithm for the vehicle routing problem[J].Computers & Operations Research,2003,30(5):787-800.
[3] 黄明,闫淑娟,梁旭.遗传算法和禁忌搜索算法在车间调度中的研究进展[J].工业控制计算机,2004,17(2):4-5.
[4] 曹二保,汤春华.车辆数目未知的带时间窗口的车辆路径混合遗传算法[J].武汉理工大学学报(交通科学与工程版),2011,35(1):33-37.
[5] 陈锋.带时间窗约束的多类型车辆路径问题的改进节约算法[J].科学技术与工程,2012,12(24):6082-6086.
[6] BERBEGLIA G ,CORDEAU J F ,LAPORTE G.Dynamic pickup and delivery problems[J].European Journal of Operational Research,2010,202(1):8-15.
[7] LAPORTE G.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,59(3):345-358.
[8] 胡金初.网络流算法的分析及研究[J].计算机科学,2009,36(1):293-294.
[9] LI B,ZHANG D,SUN L,et al.Hunting or waiting?Discovering passenger-finding strategies from a large-scale real-world taxi dataset[C].2011 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops).IEEE,2011.
[10] 法拉.基于Edmonds-Karp算法的输入排队调度[J].计算机工程,2005,31(18):13-15
[11] YANG J,JAILLET P,MAHMASSANI H.Real-time multivehicle truckload pickup and delivery problems[J].Transport Sci,2004,38(2):135 -148.
[12] BERBEGLIA G,CORDEAU JF,LAPORTE G (2010) Dynamic pickup and delivery problems[J].Eur J Oper Res,2010,202(1):8–15.
[13] Tachet R,Sagarra O,Santi P,et al.Scaling law of urban ride sharing[R].Sci.Rep.2017:42868.
[2] BAKER,BARRIE M,AYECHEW M A.A genetic algorithm for the vehicle routing problem[J].Computers & Operations Research,2003,30(5):787-800.
[3] 黄明,闫淑娟,梁旭.遗传算法和禁忌搜索算法在车间调度中的研究进展[J].工业控制计算机,2004,17(2):4-5.
[4] 曹二保,汤春华.车辆数目未知的带时间窗口的车辆路径混合遗传算法[J].武汉理工大学学报(交通科学与工程版),2011,35(1):33-37.
[5] 陈锋.带时间窗约束的多类型车辆路径问题的改进节约算法[J].科学技术与工程,2012,12(24):6082-6086.
[6] BERBEGLIA G ,CORDEAU J F ,LAPORTE G.Dynamic pickup and delivery problems[J].European Journal of Operational Research,2010,202(1):8-15.
[7] LAPORTE G.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,59(3):345-358.
[8] 胡金初.网络流算法的分析及研究[J].计算机科学,2009,36(1):293-294.
[9] LI B,ZHANG D,SUN L,et al.Hunting or waiting?Discovering passenger-finding strategies from a large-scale real-world taxi dataset[C].2011 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops).IEEE,2011.
[10] 法拉.基于Edmonds-Karp算法的输入排队调度[J].计算机工程,2005,31(18):13-15
[11] YANG J,JAILLET P,MAHMASSANI H.Real-time multivehicle truckload pickup and delivery problems[J].Transport Sci,2004,38(2):135 -148.
[12] BERBEGLIA G,CORDEAU JF,LAPORTE G (2010) Dynamic pickup and delivery problems[J].Eur J Oper Res,2010,202(1):8–15.
[13] Tachet R,Sagarra O,Santi P,et al.Scaling law of urban ride sharing[R].Sci.Rep.2017:42868.