车辆路径问题：从时间地理学的视角

doi:10.3724/SP.J.1047.2015.00022

地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (1): 22-30.doi: 10.3724/SP.J.1047.2015.00022

车辆路径问题：从时间地理学的视角

戚铭尧^1,²(), 吴涛¹, 张新³

1. 清华大学深圳研究生院物流与交通学部,深圳 518055
2. 深圳市物流工程与仿真重点实验室,深圳 518055
3. 中国科学院遥感与数字地球研究所,北京 100094

收稿日期:2014-07-07 修回日期:2014-09-06 出版日期:2015-01-10 发布日期:2015-01-05
作者简介:
作者简介：戚铭尧（1974-）,男,博士,副教授,研究方向为物流网络规划与路径规划。E-mail:qimy@sz.tsinghua.edu.cn
基金资助:
国家自然科学基金面上项目“不确定条件下移动设施路径问题的时空优化研究”（71272030）

Vehicle Routing Problem: From a Perspective of Time Geography

QI Mingyao^1,^2,^*(), WU Tao¹, ZHANG Xin³

1. Division of Logistics and Transportation, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China
2. Shenzhen Key Lab of Logistics Engineering and Simulation, Shenzhen 518055, China
3. Institute of Remote Sensing and Digital Earth, Chinese Academy of Science, Beijing 100094, China

Received:2014-07-07 Revised:2014-09-06 Online:2015-01-10 Published:2015-01-05
Contact: QI Mingyao
About author:
*The author: CHEN Nan, E-mail:fjcn99@163.com

摘要/Abstract

摘要：

车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口2个方面的特征,可更科学地判定顾客之间的“邻近性”。论文通过设计一种求解大规模软时间窗车辆路径问题的算法,证明了时空距离的价值,并展望了时间地理学在求解动态车辆路径规划问题、移动设施路径规划问题等方面的应用。本文的贡献在于,通过时间地理学所提供的一系列概念和方法,实现了在统一的框架下同时考虑车辆路径问题（VRP）的时间和空间特征的构想,挖掘了传统时间地理学理论在车辆路径领域中的应用潜力,这将有利于更快或者更好地求解VRP问题。

关键词: 车辆路径问题, 时间地理学, 时空可达性, 物流, GIS

Abstract:

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

戚铭尧, 吴涛, 张新. 车辆路径问题：从时间地理学的视角[J]. 地球信息科学学报, 2015, 17(1): 22-30.DOI:10.3724/SP.J.1047.2015.00022

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

图/表 8

图1

图2

图3

图4

图5

图6

图7

表1

参考文献 39

[1]	Dantzig G B, Ramser J H.The truck dispatching problem[J]. Management Science, 1959,6(1):80-91.
[2]	Hägerstrand T.What about people in regional science[J]. Papers and Proceedings of the Regional Science Association, 1970,24:7-21.
[3]	Martensson S.Childhood interaction and temporal organization[J]. Economic Geography, 1977,2:99-125.
[4]	Pred A.The impact of technological and institutional innovations on life content: Time geographic observations[J]. Geography Analysis, 1978,10:345-372.
[5]	Miller R.Household activity [atterns in nineteenth-century suburbs: A time-geographic exploration[J]. Annals of the Association of American Geographers, 1982,72:355-371.
[6]	Forer P C, Kivell H.Space time budgets, public transport, and spatial choice[J]. Environment and Planning A, 1981,13:497-509.
[7]	Pred A, Palm R.The status of american women: A time geographic view[M]//Lanegran D A, Palm R. Invitation to Geography. New York: Mcgraw2Hill, 1978:99-109.
[8]	Kwan M P.Gender, the home-work link, and space-time patterns of non-employment activities[J]. Economic Geography, 1999,75(4):370-394.
[9]	Lenntorp B.Time-geography——At the end of its beginning[J]. GeoJournal, 1999,48:155-158.
[10]	Lenntorp B.A time geographic simulation model of individual activity programs[M]//Carlstein T, et al. Timing Space and Spacing Time, Vol.2: Human Activity and Time Geography. London: Edward Arnold, 1978:162-180.
[11]	Miller H J.Modeling accessibility using space-time prism concepts within geographical information systems[J]. International Journal of Geographical Information Systems, 1991,5(3):287-301.
[12]	Kwan M P, Hong X D.Network-based constraints-oriented choice set formation using GIS[J]. Geographical Systems, 1998,5:139-162.
[13]	Kwan M P.Space-time and integral measures of individual accessibility: A comparative analysis using a point-based framework[J]. Geographical Analysis, 1998,30(3):191-216.
[14]	Miller H J, Wu Y H.GIS software for measuring space-time accessibility in transportation planning and analysis[J]. GeoInformatica, 2000,4(2):141-159.
[15]	Kwan M P, Weber J.Individual accessibility revisited: Implications for geographical analysis in the twenty-first century[J]. Geographical Analysis, 2003,35(4):341-353.
[16]	Miller H J.A measurement theory for time geography[J]. Geographical Analysis, 2005,37(1):17-45.
[17]	Shaw S L, Yu H, Bombom L. A space-time GIS approach to exploring large individual-based spatiotemporal datasets[J]. Transactions in GIS, 2008,12(4):425-441.
[18]	Shaw S L, Yu H.A GIS-based time-geographic approach of studying individual activities and interactions in a hybrid physical-virtual space[J]. Journal of Transport Geography, 2009,17(2):141-149.
[19]	Kwan M P, Lee J.Geovisualization of human activity patterns using 3D GIS: A time-geographic approach[M]// Goodchild M F, Janelle D G. Spatially Integrated Social Science. Oxford University Press: New York, 2004:48-66.
[20]	Kraak M J, Koussoulakou A.A visualization environment for the space-time cube[C]. SDH 2004: Proceedings of the 11th International Symposium on Spatial Data Handling: Advances in Spatial Data Handling II: 23-25 August 2004, University of Leichester, 2004:189-200.
[21]	Yu H.Spatial-temporal GIS design for exploring interactions of human activities[J]. Cartography and Geographic Information Science, 2006,33(1):3-19.
[22]	Yu H.Visualizing and analyzing activities in an integrated space-time environment: Temporal GIS design and implementation[J]. Transportation Research Record: Journal of the Transportation Research Board, 2007,2024:54-62.
[23]	Yu H, Shaw S L.Exploring potential human activities in physical and virtual spaces: A spatio-temporal GIS approach[J]. International Journal of Geographic Information Science, 2008,22(4):409-430.
[24]	戚铭尧,樊艳伟,彭昕,等.一种基于交通网络的时空棱柱表示[J].武汉大学学报(信息科学版),2010,12(35):1491-1495.
[25]	Neutens T, Witlox F, Demaeyer P.Individual accessibility and travel possibilities: A literature review on time geography[J]. European Journal of Transport and Infrastructure Research, 2007,7(4):335-352.
[26]	刘钊,罗智德,张耀方,等.基于时空棱柱的人员搜寻范围优化[J].地球信息科学学报,2014,16(4):531-536.
[27]	Solomon M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987,35(2):254-265.
[28]	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.
[29]	Pirie G H.Measuring accessibility: A review and proposal[J]. Environment and Planning A, 1979,11(3):299-312.
[30]	Morris J M, Dumble P, Wigan M.Accessibility indicators for transportation planning[J]. Transportation Research A, 1979,13:91-109.
[31]	Kim H M, Kwan M P.Space-time accessibility measures: A geocomputational algorithm with a focus on the feasible opportunity set and possible activity duration[J]. Journal of Geographical Systems, 2003,5(1):71-91.
[32]	Kwan M P, Alan T, Murray M E, et al.Recent advances in accessibility research: Representation, methodology and applications[J]. Journal of Geographical Systems, 2003,5(1):129-138.
[33]	Miller H J.Measuring space-time accessibility beneﬁts within transportation networks: Basic theory and computational methods[J]. Geographical Analysis, 1999,31:187-212.
[34]	Weber J.Individual accessibility and distance from major employment centers: An examination using space-time measures[J]. Journal of Geographical Systems, 2003,5:51-70.
[35]	Weber J, Kwan M P.Bringing time back in: A study on the influence of travel time variations and facility opening hours on individual accessibility[J]. The Professional Geographer, 2002,54:226-240.
[36]	Weber J, Kwan M P.Evaluating the effects of geographic contexts on individual accessibility: A multilevel approach[J]. Urban Geography, 2003,24:647-671.
[37]	涂伟,方志祥,李清泉,等. 基于Voronoi邻近的物流车辆路径快速优化算法[J].地球信息科学学报,2012,14(6):781-787.
[38]	Qi M Y, Lin W H, Li N, et al.A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows[J]. Transportation Research: Part B, 2012,48:248-257.
[39]	任丽. 基于时空聚类的车辆路径分析与优化[D].北京:清华大学,2011.

算例	基于空间距离				基于时空距离
算例	车辆数	费用	等待时间(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

车辆路径问题：从时间地理学的视角

Vehicle Routing Problem: From a Perspective of Time Geography

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 39

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	孙银萍, 张兴国, 石新雨, 李奇泽. 顾及视频地理映射的人群密度估计方法[J]. 地球信息科学学报, 2022, 24(6): 1130-1138.
[2]	张志锟, 范俊甫, 徐少波, 陈政. 多边形叠加Vatti算法的VCS优化方法与GPU并行化[J]. 地球信息科学学报, 2022, 24(3): 437-447.
[3]	刘琳琳, 郑伯红, 骆晨. 基于交通大数据的南昌市中心城区等时圈划分及特征分析[J]. 地球信息科学学报, 2022, 24(2): 220-234.
[4]	王烁棋, 赵亮. 山城眺望空间OSCA模型构建及应用[J]. 地球信息科学学报, 2021, 23(9): 1559-1574.
[5]	王杏锋, 李代超, 吴升, 谢晓苇, 卢嘉奇. 水稻种植环境综合适宜性评价方法研究[J]. 地球信息科学学报, 2021, 23(8): 1484-1496.
[6]	李清嘉, 彭建东, 杨红. 武汉市不同站域建成环境与轨道交通站点客流特征关系分析[J]. 地球信息科学学报, 2021, 23(7): 1246-1258.
[7]	廖心治, 王华, 赵万民. 融合地图数据的山地城市医疗设施服务覆盖评估方法研究[J]. 地球信息科学学报, 2021, 23(4): 604-616.
[8]	曹中浩, 张健钦, 杨木, 贾礼朋, 邓少存. 基于GIS新冠智能体仿真模型及应用——以广州市为例[J]. 地球信息科学学报, 2021, 23(2): 297-306.
[9]	胡毅荣, 王超, 杜震洪, 张丰, 刘仁义. 一种与地图服务结合的栅格瓦片计算模型[J]. 地球信息科学学报, 2021, 23(10): 1756-1766.
[10]	宋关福, 陈勇, 罗强, 武梦瑶. GIS基础软件技术体系发展及展望[J]. 地球信息科学学报, 2021, 23(1): 2-15.
[11]	李锐, 石佳豪, 董广胜, 刘朝辉. 多粒度时空对象组成结构表达研究[J]. 地球信息科学学报, 2021, 23(1): 113-123.
[12]	姚可桢, 岳书平. 网络大数据下的中国现代食甜习惯空间分布特征及其影响因素研究[J]. 地球信息科学学报, 2020, 22(6): 1202-1215.
[13]	朱亚茹, 高峻, 邴振华, 张中浩, 付晶. 基于参与式制图方法的景观服务评估与空间结构研究[J]. 地球信息科学学报, 2020, 22(5): 1106-1119.
[14]	赵耀龙, 巢子豪. 历史GIS的研究现状和发展趋势[J]. 地球信息科学学报, 2020, 22(5): 929-944.
[15]	王英杰, 张桐艳, 李鹏, 虞虎. GIS在中国旅游资源研究与应用中的现状及趋势[J]. 地球信息科学学报, 2020, 22(4): 751-759.