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

Vehicle Routing Problem: From a Perspective of Time Geography

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

Vehicle routing problem （VRP） has typical characteristics of space-time distribution, thus it is influ-enced 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 ve-hicle routing problem and introduced a complete analytic framework from the aspects of time geography. Fol-lowed by the introduction of the fundamental theory of time geography, concepts including space-time con-straints, 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 addi-tion, 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 be-tween 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 ef-forts 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.