货运配载VRP问题的路径匹配算法
摘要
货运配载是在我国交通运输行业特定历史环境下产生的一种运输模式,它为提高我国公路运输效率做出了巨大贡献。这种运输模式中,最关键的环节之一是配货信息的交流。传统配货信息的交流主要是通过分布于道路两侧的“空车配货站”进行,这种信息交流方式效率低下,经常会出现有货源信息但一时又找不到合适的车辆信息,有了车辆信息却找不到货源信息的状态,丧失了许多交易机会。为此,交通部公路科学院在1998年投资1000多万元建设了华夏交通在线,开展网络配载业务,随后几年,又有多个配货网站投入运营。利用互联网进行配货信息交流,拓宽了货源信息交流渠道,有助于配载交易形成,在一定程度上降低了空载率,提高了运输效率,无疑是空车配货模式发展的正确方向。但是,这种通过网页浏览的方式来对海量配货信息进行发布和检索效率仍然不高,迫切需要一种能够自动根据路径特点对配货信息进行筛选的信息检索方式。
货运配载的路径匹配问题,属于开放型车辆路径问题(Open Vehicle RoutingProblem,OVRP)的一类。但目前对车辆路径问题的研究大多面向数学模型,通常需要较长的建模与计算时间,是面向离线的、非实时的应用,并不能直接应用于求解我国货运配载路径信息匹配的实际问题。
针对此情况,本文在充分调研我国货运配载的产生发展和运营过程的基础上,对近几年出现的网络配载模式及功能进行深入分析,引入网络图模型,提出了一个基于交通路网的路径匹配算法。该算法利用交通路网中各结点之间的距离关系,可以检索给定起迄点间及起迄点与各自邻近结点群之间存在的配货信息,同时规划出收益费用比最优的行驶路径,并能根据配货行驶路径的特点对检索出的所信息进行分析、评价和优选,以方便配货组织。文章除了对算法思想和算法描述进行了详细介绍外,还对算法的时空复杂度进行了分析,以证实算法的可行性。最后,文章有重点地介绍了算法仿真实现所需的数据结构、功能函数和部分关键代码。
Freight transportation load matching is a kind of transportation modes in traffic transport industry with particular historical circumstance, which made great contributes for raising transportation efficiency. During this transportation mode, one of the most important links is information communication. Traditional communication of freight load matching information is mainly through freight transportation stations on both sides of road. This results low efficiency or lose trading opportunity, because sometimes cannot find proper vehicle when exist supply of goods, and also sometimes just in contrary. Therefore, in 1998 ministry of communication invested 10 billion to contribute HuaXia transport online, developing stowage with network. In subsequent years, a few more website was put into operation. Freight load matching information communicating with network can widen channel, benefit to transaction, reduce no-load rate to some extent, and improve transport efficiency, which is the correct direction of freight load matching transportation mode. However, publish and select information through browsing web page is stile in low rate, so we need a new auto select method based on rout characters.
Freight load matching routing matching problem belongs to a kind of open vehicle routing problem. At present, the research of these problems often oriented to mathematic model, which need a long time to set up the model and calculate. This is not on real-time, and cannot solve the actual freight transportation load matching problems directly.
According to this situation, investigating the production, development and operation of freight transpiration in our country sufficiently, the thesis evaluates stowage mode with website and the function, introducing network graph mode, and proposes a path matching algorithm based on traffic network. The algorithm which using the distance relation of the nodes in the traffic network, can search information of freight trips between given O D points and trips which intersect groups of adjacent points respectively of O D points, calculate the freight route with best benefit cost ratio separately, also can analyze and evaluate and filter these information in the light of characteristic of freight route so that the load matching be convenient. Besides introducing the thought of the algorithm, the thesis also analyzes the complexity in time and space, in order to calculate the availability. In the end, the thesis introduces necessary data structure, performance function and some key code in this algorithm.
货运配载的路径匹配问题,属于开放型车辆路径问题(Open Vehicle RoutingProblem,OVRP)的一类。但目前对车辆路径问题的研究大多面向数学模型,通常需要较长的建模与计算时间,是面向离线的、非实时的应用,并不能直接应用于求解我国货运配载路径信息匹配的实际问题。
针对此情况,本文在充分调研我国货运配载的产生发展和运营过程的基础上,对近几年出现的网络配载模式及功能进行深入分析,引入网络图模型,提出了一个基于交通路网的路径匹配算法。该算法利用交通路网中各结点之间的距离关系,可以检索给定起迄点间及起迄点与各自邻近结点群之间存在的配货信息,同时规划出收益费用比最优的行驶路径,并能根据配货行驶路径的特点对检索出的所信息进行分析、评价和优选,以方便配货组织。文章除了对算法思想和算法描述进行了详细介绍外,还对算法的时空复杂度进行了分析,以证实算法的可行性。最后,文章有重点地介绍了算法仿真实现所需的数据结构、功能函数和部分关键代码。
Freight transportation load matching is a kind of transportation modes in traffic transport industry with particular historical circumstance, which made great contributes for raising transportation efficiency. During this transportation mode, one of the most important links is information communication. Traditional communication of freight load matching information is mainly through freight transportation stations on both sides of road. This results low efficiency or lose trading opportunity, because sometimes cannot find proper vehicle when exist supply of goods, and also sometimes just in contrary. Therefore, in 1998 ministry of communication invested 10 billion to contribute HuaXia transport online, developing stowage with network. In subsequent years, a few more website was put into operation. Freight load matching information communicating with network can widen channel, benefit to transaction, reduce no-load rate to some extent, and improve transport efficiency, which is the correct direction of freight load matching transportation mode. However, publish and select information through browsing web page is stile in low rate, so we need a new auto select method based on rout characters.
Freight load matching routing matching problem belongs to a kind of open vehicle routing problem. At present, the research of these problems often oriented to mathematic model, which need a long time to set up the model and calculate. This is not on real-time, and cannot solve the actual freight transportation load matching problems directly.
According to this situation, investigating the production, development and operation of freight transpiration in our country sufficiently, the thesis evaluates stowage mode with website and the function, introducing network graph mode, and proposes a path matching algorithm based on traffic network. The algorithm which using the distance relation of the nodes in the traffic network, can search information of freight trips between given O D points and trips which intersect groups of adjacent points respectively of O D points, calculate the freight route with best benefit cost ratio separately, also can analyze and evaluate and filter these information in the light of characteristic of freight route so that the load matching be convenient. Besides introducing the thought of the algorithm, the thesis also analyzes the complexity in time and space, in order to calculate the availability. In the end, the thesis introduces necessary data structure, performance function and some key code in this algorithm.
引文
1.曲衍国.公路物流运输中的汽车利用效率问题[J],综合运输,2004,(6):52-55
2.苗壮,金俊武.空车配货信息中介服务[J],中国软科学,2001,(7):79-81
3.孟宇坤.区域道路货运市场信息平台的系统分析与设计[D],北京:北京交通大学,2006
4.张文建,杨拴强.基于B/S模式的一体化物流管理信息系统的开发与研究[J],矿山机械,2006,34(4):8-9
5.简林莎,段宗涛,周兴社.智能运输系统信息平台[J],长安大学学报(自然科学版),2006,26(2):81-83
6.宋延,石建军,王海忠.智能运输系统在现代物流中的应用[J],道路交通与安全,2005,(1):14-16
7.王喜富,申金升,关伟.区域性现代物流公共信息平台系统框架研究[J],物流技术,2006,(1):77-79
8.赵振峰,崔南方,陈荣秋.区域公共物流信息平台的功能定位及运行机制研究[J],物流技术,2004,(4):63-66
9.李玉民,刘珊中,李旭宏.区域物流信息平台框架分析.河南科技大学学报(自然科学版)[J],2004,25(1):65-68
10.陈火根,张建林,程耀东.在线货物配载网格服务模型与方法研究[J],浙江大学学报(工学版),2008,42(2):243-247
11.萸晋 白杉.从空驶货运车辆谈起[J],中国储运,2002,(2):24
12.苗壮,徐俊彦.空车配货信息服务网络规模经济[J],公路交通科技,2002,19(1):137-139
13.栾惠民.货运信息(配载)业的发展[J],辽宁交通科技,1999,(4):52-53
14.曾俊伟,吕斌,张铭.公路货运配载系统的研究与设计[J],物流科技,2006,29(10):49-51
15.Dantzig G B,Ramser J H,"The truck dispatching problem" Management Science,1959(6):80
16.Clarcke G,Wright J V,"Scheduling of vehicles from a central depot to a number of delivery points" Operations Research,1964(12):568-581
17.Canen A.G,Scott L.G,"Bridging theory and practice in VRP" Journal of the Operational Research Soeiety,1995,46(1):1-8
18.符卓.开放式车辆路径问题及其应用研究[D],湖南长沙:中南大学,2003
19.孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J],系统工程,2006,24(11):31-37
20.Fisher M L.Optimal solution of vehicle routing problems using minimumk-trees[J],Operations Research,1994,42(4):141-153
21.Padberg M,Rinaldi G.A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems[J],SIAM Review,1991,33(1):60-100
22.Kohl N,Madsen O B G.An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J],Operations Research,1997,45(3):395-406
23.Fumero F.A modified subgradient algorithm for Lagrangean relaxation[J],Computers and Operations Research,2000,28(1):33-52
24.Lorena Luiz A N,Senne Edson L F.A column generation approach to capacitated p-median problems[J]Computers and Operations Research,2004,31(6):863-876
25.Clarke G,Wright J W.Scheduling of vehicles from a central depot to a number of delivery points[J],Operations Research,1964,12(4):568-581
26.Gillett B E,Miller L R.A heuristic algorithm for the vehicle-dispatch problem[J],Operations Research,1974,22(2):240-349
27.Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constrains[J],Operations Research,1987,35(2):254-265
28.Lin S.Computer solutions of the traveling salesman problem[J],Bell System Technical Journal,1965,44(10):2245-2269
29.Taillard E,Badeau P,Gendreau M,Guertin F,Potvin J Y.A tabu search heuristic for the vehicle routing problem with soft time windows[J],Transportation Science,1997,31(2):170-186
30.Potvin J Y,Kervahut T,Gareau B I,Rousseau J M.The vehicle routing problem with time windows, Part I: Tabu search[J], INFORMS Journal on Computing, 1996, 8(2):158-164
31. Potvin J Y, Bengio S. The vehicle routing problem with time windows,Part II:genetic search[J], Informs Journal on Computing,1996,8(2):165-172
32. Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J], Annals of Operations Research, 1993, 41(4):421-451
33. Tan K C, Lee L H, Zhu Q L, Ou K. Heuristic methods for vehicle routing problem with time windows[J], Artificial Intelligence in Engineering,2001,15(3):281-295
34. Glover F. Tabu search:part I[J], Journal on Computing, 1989,1(3):190-206
35. Chao I M. A tabu search method for the truck and trailer routing problem [J], Computers & Operations Research,2002,29(1):33-51
36. Scheuerer S. A tabu search heuristic for the truck and trailer routing problem[J],Computers &Operations Research,2006,33(4):894-909
37. Brandao J. A tabu search algorithm for the open vehicle routing problem[J], European Journal of Operational Research,2004,157(3):552-564
38. Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J], Computers &Operations Research,2004,31(12):1947-1964
39. Montane F A T, Galvao R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J], Computers &Operations Research,2006,33(3):595-619
40. Kirkpatrick S,Gelatt C D,Vechi Jr M P. Optimization by simulated annealing[J],Science,1983,220(4598):671-680
41. Ululgu L E, Teghem J. Multiobjective combinatorial optimization problems:a survey[J],Journal of Multicriteria Decision Analysis,1994,3(2):83-104
42. Berger J, Barkaoui M, Ollibraysy. A route-directed hybrid genetic approach for the vehicle routing problem with time windows[J], INFOR,2003, 41(2):179-194
43. Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J], Computers &Operations Research,2004, 31(12):2037-2053
44. Dorigo M,Gambardella L M. Ant colony system:a cooperative learning approach to the traveling salesman problem[J], IEEE Trans Evolutionary Computation, 1997,1(1):53-66
45. Bullnheimer B,Hartl R F,Strauss C. An improved ant system algorithm for the vehicle routing problem[J], Annals of Operations Research,1999,89:319-328
46. Mazzeo S, Loiseau I. An ant colony algorithm for the capacitated vehicle routing[J],Electronic Notes in Discrete Mathematics,2004,18:181-186
47. D Sariklis and S Powell. A heuristic method for the open vehicle routing problem[J],Journal of the Operational Research Society,2000,51:564-573
2.苗壮,金俊武.空车配货信息中介服务[J],中国软科学,2001,(7):79-81
3.孟宇坤.区域道路货运市场信息平台的系统分析与设计[D],北京:北京交通大学,2006
4.张文建,杨拴强.基于B/S模式的一体化物流管理信息系统的开发与研究[J],矿山机械,2006,34(4):8-9
5.简林莎,段宗涛,周兴社.智能运输系统信息平台[J],长安大学学报(自然科学版),2006,26(2):81-83
6.宋延,石建军,王海忠.智能运输系统在现代物流中的应用[J],道路交通与安全,2005,(1):14-16
7.王喜富,申金升,关伟.区域性现代物流公共信息平台系统框架研究[J],物流技术,2006,(1):77-79
8.赵振峰,崔南方,陈荣秋.区域公共物流信息平台的功能定位及运行机制研究[J],物流技术,2004,(4):63-66
9.李玉民,刘珊中,李旭宏.区域物流信息平台框架分析.河南科技大学学报(自然科学版)[J],2004,25(1):65-68
10.陈火根,张建林,程耀东.在线货物配载网格服务模型与方法研究[J],浙江大学学报(工学版),2008,42(2):243-247
11.萸晋 白杉.从空驶货运车辆谈起[J],中国储运,2002,(2):24
12.苗壮,徐俊彦.空车配货信息服务网络规模经济[J],公路交通科技,2002,19(1):137-139
13.栾惠民.货运信息(配载)业的发展[J],辽宁交通科技,1999,(4):52-53
14.曾俊伟,吕斌,张铭.公路货运配载系统的研究与设计[J],物流科技,2006,29(10):49-51
15.Dantzig G B,Ramser J H,"The truck dispatching problem" Management Science,1959(6):80
16.Clarcke G,Wright J V,"Scheduling of vehicles from a central depot to a number of delivery points" Operations Research,1964(12):568-581
17.Canen A.G,Scott L.G,"Bridging theory and practice in VRP" Journal of the Operational Research Soeiety,1995,46(1):1-8
18.符卓.开放式车辆路径问题及其应用研究[D],湖南长沙:中南大学,2003
19.孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J],系统工程,2006,24(11):31-37
20.Fisher M L.Optimal solution of vehicle routing problems using minimumk-trees[J],Operations Research,1994,42(4):141-153
21.Padberg M,Rinaldi G.A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems[J],SIAM Review,1991,33(1):60-100
22.Kohl N,Madsen O B G.An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J],Operations Research,1997,45(3):395-406
23.Fumero F.A modified subgradient algorithm for Lagrangean relaxation[J],Computers and Operations Research,2000,28(1):33-52
24.Lorena Luiz A N,Senne Edson L F.A column generation approach to capacitated p-median problems[J]Computers and Operations Research,2004,31(6):863-876
25.Clarke G,Wright J W.Scheduling of vehicles from a central depot to a number of delivery points[J],Operations Research,1964,12(4):568-581
26.Gillett B E,Miller L R.A heuristic algorithm for the vehicle-dispatch problem[J],Operations Research,1974,22(2):240-349
27.Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constrains[J],Operations Research,1987,35(2):254-265
28.Lin S.Computer solutions of the traveling salesman problem[J],Bell System Technical Journal,1965,44(10):2245-2269
29.Taillard E,Badeau P,Gendreau M,Guertin F,Potvin J Y.A tabu search heuristic for the vehicle routing problem with soft time windows[J],Transportation Science,1997,31(2):170-186
30.Potvin J Y,Kervahut T,Gareau B I,Rousseau J M.The vehicle routing problem with time windows, Part I: Tabu search[J], INFORMS Journal on Computing, 1996, 8(2):158-164
31. Potvin J Y, Bengio S. The vehicle routing problem with time windows,Part II:genetic search[J], Informs Journal on Computing,1996,8(2):165-172
32. Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J], Annals of Operations Research, 1993, 41(4):421-451
33. Tan K C, Lee L H, Zhu Q L, Ou K. Heuristic methods for vehicle routing problem with time windows[J], Artificial Intelligence in Engineering,2001,15(3):281-295
34. Glover F. Tabu search:part I[J], Journal on Computing, 1989,1(3):190-206
35. Chao I M. A tabu search method for the truck and trailer routing problem [J], Computers & Operations Research,2002,29(1):33-51
36. Scheuerer S. A tabu search heuristic for the truck and trailer routing problem[J],Computers &Operations Research,2006,33(4):894-909
37. Brandao J. A tabu search algorithm for the open vehicle routing problem[J], European Journal of Operational Research,2004,157(3):552-564
38. Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J], Computers &Operations Research,2004,31(12):1947-1964
39. Montane F A T, Galvao R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J], Computers &Operations Research,2006,33(3):595-619
40. Kirkpatrick S,Gelatt C D,Vechi Jr M P. Optimization by simulated annealing[J],Science,1983,220(4598):671-680
41. Ululgu L E, Teghem J. Multiobjective combinatorial optimization problems:a survey[J],Journal of Multicriteria Decision Analysis,1994,3(2):83-104
42. Berger J, Barkaoui M, Ollibraysy. A route-directed hybrid genetic approach for the vehicle routing problem with time windows[J], INFOR,2003, 41(2):179-194
43. Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J], Computers &Operations Research,2004, 31(12):2037-2053
44. Dorigo M,Gambardella L M. Ant colony system:a cooperative learning approach to the traveling salesman problem[J], IEEE Trans Evolutionary Computation, 1997,1(1):53-66
45. Bullnheimer B,Hartl R F,Strauss C. An improved ant system algorithm for the vehicle routing problem[J], Annals of Operations Research,1999,89:319-328
46. Mazzeo S, Loiseau I. An ant colony algorithm for the capacitated vehicle routing[J],Electronic Notes in Discrete Mathematics,2004,18:181-186
47. D Sariklis and S Powell. A heuristic method for the open vehicle routing problem[J],Journal of the Operational Research Society,2000,51:564-573