地球信息科学学报
地毬信息科學學報
지구신식과학학보
GEO-INFORMATION SCIENCE
2015年
1期
22-30
,共9页
车辆路径问题%时间地理学%时空可达性%物流%GIS
車輛路徑問題%時間地理學%時空可達性%物流%GIS
차량로경문제%시간지이학%시공가체성%물류%GIS
vehicle routing problem%time geography%space-time accessibility%logistics%GIS
车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口2个方面的特征,可更科学地判定顾客之间的“邻近性”。论文通过设计一种求解大规模软时间窗车辆路径问题的算法,证明了时空距离的价值,并展望了时间地理学在求解动态车辆路径规划问题、移动设施路径规划问题等方面的应用。本文的贡献在于,通过时间地理学所提供的一系列概念和方法,实现了在统一的框架下同时考虑车辆路径问题(VRP)的时间和空间特征的构想,挖掘了传统时间地理学理论在车辆路径领域中的应用潜力,这将有利于更快或者更好地求解VRP问题。
車輛路徑問題具有典型的時空分佈特徵,受到衆多時空約束條件的製約。在車輛路徑規劃中,綜閤攷慮時間和空間因素是非常必要的。本文從時間地理學這一全新的視角來研究車輛路徑問題,提齣一套完整的時間地理學分析框架,闡述瞭時間地理學的基本概唸,提齣瞭車輛路徑問題中的時空約束、時空路徑、時空稜柱、時空可達性、時空距離等概唸,併給齣瞭圖示或定量化的度量方法。論文提齣的時空距離度量方法綜閤攷慮瞭顧客在空間位置和時間窗口2箇方麵的特徵,可更科學地判定顧客之間的“鄰近性”。論文通過設計一種求解大規模軟時間窗車輛路徑問題的算法,證明瞭時空距離的價值,併展望瞭時間地理學在求解動態車輛路徑規劃問題、移動設施路徑規劃問題等方麵的應用。本文的貢獻在于,通過時間地理學所提供的一繫列概唸和方法,實現瞭在統一的框架下同時攷慮車輛路徑問題(VRP)的時間和空間特徵的構想,挖掘瞭傳統時間地理學理論在車輛路徑領域中的應用潛力,這將有利于更快或者更好地求解VRP問題。
차량로경문제구유전형적시공분포특정,수도음다시공약속조건적제약。재차량로경규화중,종합고필시간화공간인소시비상필요적。본문종시간지이학저일전신적시각래연구차량로경문제,제출일투완정적시간지이학분석광가,천술료시간지이학적기본개념,제출료차량로경문제중적시공약속、시공로경、시공릉주、시공가체성、시공거리등개념,병급출료도시혹정양화적도량방법。논문제출적시공거리도량방법종합고필료고객재공간위치화시간창구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.