Journal of Geo-information Science >
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
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
QI Mingyao , WU Tao , ZHANG Xin . Vehicle Routing Problem: From a Perspective of Time Geography[J]. Journal of Geo-information Science, 2015 , 17(1) : 22 -30 . DOI: 10.3724/SP.J.1047.2015.00022
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] |
|
/
〈 |
|
〉 |