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

• • 上一篇    下一篇

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

戚铭尧1,2(), 吴涛1, 张新3   

  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 Mingyao1,2,*(), WU Tao1, ZHANG Xin3   

  1. 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 E-mail:qimy@sz.tsinghua.edu.cn
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

摘要:

车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口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