车辆路径问题:从时间地理学的视角
作者简介:戚铭尧(1974-),男,博士,副教授,研究方向为物流网络规划与路径规划。E-mail:qimy@sz.tsinghua.edu.cn
收稿日期: 2014-07-07
要求修回日期: 2014-09-06
网络出版日期: 2015-01-05
基金资助
国家自然科学基金面上项目“不确定条件下移动设施路径问题的时空优化研究”(71272030)
Vehicle Routing Problem: From a Perspective of Time Geography
Received date: 2014-07-07
Request revised date: 2014-09-06
Online published: 2015-01-05
Copyright
车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口2个方面的特征,可更科学地判定顾客之间的“邻近性”。论文通过设计一种求解大规模软时间窗车辆路径问题的算法,证明了时空距离的价值,并展望了时间地理学在求解动态车辆路径规划问题、移动设施路径规划问题等方面的应用。本文的贡献在于,通过时间地理学所提供的一系列概念和方法,实现了在统一的框架下同时考虑车辆路径问题(VRP)的时间和空间特征的构想,挖掘了传统时间地理学理论在车辆路径领域中的应用潜力,这将有利于更快或者更好地求解VRP问题。
戚铭尧 , 吴涛 , 张新 . 车辆路径问题:从时间地理学的视角[J]. 地球信息科学学报, 2015 , 17(1) : 22 -30 . DOI: 10.3724/SP.J.1047.2015.00022
Vehicle routing problem (VRP) has typical characteristics of space-time distribution, thus it is influenced by constrains of space-time conditions. It is necessary to take the space and time factors comprehensively into the consideration of vehicle routing planning. In this paper, we proposed a new perspective to investigate vehicle routing problem and introduced a complete analytic framework from the aspects of time geography. Followed by the introduction of the fundamental theory of time geography, concepts including space-time constraints, space-time path, space-time prism, space-time accessibility, and space-time distance are illustrated in the context of VRP. Meanwhile, the diagrammatic and metric methods of these concepts are also provided. In addition, this paper developed a method to calculate space-time distance. This method considers the characteristics of both locations and time windows for different customers, thus it can be used to easily evaluate the proximity between customers. Finally, we illustrate the value and advantage of time geography by presenting an algorithm to solve a large-scale VRP with soft time windows, embedding the concept of spatio-temporal distance. Further efforts may be devoted to adopt time geography to solve real-time VRP and mobile facility routing problem, etc. The main contribution of this paper is that we find the potential and possibility of time geography in solving VRP problems. Using a series of conceptions and methods of time geography, we can integrate both spatial and temporal features of VRP in a unified frame, which could make solving the VRP problems to be more efficient and effective.
Key words: vehicle routing problem; time geography; space-time accessibility; logistics; GIS
Fig. 1 A solution to a VRP instance图1 一个VRP实例的解决方案 |
Fig. 2 Two space-time routes based on the real transportation network图2 真实交通网络的时空路径 |
Fig. 3 Space-time prism图3 时空棱柱 |
Fig. 4 Space-time routes of two vehicles in a VRP instance图4 包含两辆车的VRP时空路径 |
Fig. 5 A space-time prism in a VRP instance图5 VRP实例中的时空棱柱 |
Fig. 6 The space-time accessibility of a vehicle in transit图6 在途车辆的空间可达范围 |
Fig. 7 The time windows of two customers图7 2个顾客时间窗之间的关系 |
Tab. 1 Computational comparison of the VRP algorithms between spatial distance and spatio-temporal distance表1 采用空间距离和时空距离的VRP算法效果对比 |
算例 | 基于空间距离 | 基于时空距离 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
车辆数 | 费用 | 等待时间(s) | 晚到时间(s) | 车辆数 | 费用 | 减少比例(%) | 等待时间(s) | 减少比例(%) | 晚到时间(s) | 减少比例(%) | |
r110_1 | 96 | 1733292.0 | 55425.8 | 529240.6 | 97 | 906176.6 | -47.7 | 18767.8 | -66.1 | 318867.9 | -39.7 |
r110_2 | 95 | 1447089.1 | 52428.1 | 387681.7 | 97 | 1001592.6 | -30.8 | 40802.6 | -22.2 | 225838.9 | -41.7 |
r110_3 | 96 | 1156667.1 | 65600.8 | 201966.8 | 95 | 966187.8 | -16.5 | 53328.4 | -18.7 | 161426.5 | -20.1 |
r110_4 | 97 | 657554.4 | 57327.6 | 58423.0 | 96 | 754247.5 | 14.7 | 60750.8 | 6.0 | 51716.1 | -11.5 |
r110_5 | 96 | 1658948.7 | 44516.1 | 516980.2 | 96 | 831090.9 | -49.9 | 18563.1 | -58.3 | 297474.5 | -42.5 |
r110_6 | 96 | 1498153.4 | 59679.4 | 339907.1 | 95 | 1090445.3 | -27.2 | 45092.9 | -24.4 | 241196.2 | -29.0 |
r110_7 | 97 | 1128792.5 | 62913.7 | 170869.0 | 96 | 999666.0 | -11.4 | 54165.1 | -13.9 | 131242.6 | -23.2 |
r110_8 | 96 | 544617.2 | 49471.3 | 58731.5 | 97 | 608456.5 | 11.7 | 50131.8 | 1.3 | 53238.3 | -9.4 |
r110_9 | 97 | 1637284.8 | 55915.6 | 471687.5 | 95 | 816374.6 | -50.1 | 18135.8 | -67.6 | 283935.6 | -39.8 |
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|
[23] |
|
[24] |
|
[25] |
|
[26] |
|
[27] |
|
[28] |
|
[29] |
|
[30] |
|
[31] |
|
[32] |
|
[33] |
|
[34] |
|
[35] |
|
[36] |
|
[37] |
|
[38] |
|
[39] |
|
/
〈 |
|
〉 |