Multiple Path Based Vehicle Routing in Dynamic and Stochastic Transportation Networks
(주)학지사
- 최초 등록일
- 2015.03.25
- 최종 저작일
- 2000.01
- 23페이지/
어도비 PDF
- 가격 5,200원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
* 본 문서는 배포용으로 복사 및 편집이 불가합니다.
서지정보
ㆍ발행기관 : 대한교통학회
ㆍ수록지정보 : 대한교통학회지 / 37권
ㆍ저자명 : Dongjoo Park
목차
Ⅰ. INTRODUCTION
Ⅱ. NOTATIONS AND PROBLEM FORMULATION
Ⅲ. MODELING CONSIDERATIONS AND ASSUMPTIONS
Ⅳ. CONTEXT-DEPENDENT WEIGHTING-BASED PRUNING TECHNIQUE
Ⅴ. SOLUTION ALGORITHMS
Ⅵ. COMPUTATIONAL EXPERIENC: CASE STUDIES
Ⅶ. CONCLUDING REMARKS
REFERENCES
한국어 초록
In route guidance systems fastest-path routing has typically been adopted because of its simplicity. However, empirical studies on route choice behavior have shown that drivers use numerous criteria in choosing a route. The objective of this study is to develop computationally efficient algorithms for identifying a manageable subset of the nondominated (i.e. Pareto optimal) paths for real-time vehicle routing which reflect the drivers' preferences and route choice behaviors. We propose two pruning algorithms that reduce the search area based on a context-dependent linear utility function and thus reduce the computation time. The basic notion of the proposed approach is that i) enumerating all nondominated paths is computationally too expensive, ii) obtaining a stable mathematical representation of the drivers' utility function is theoretically difficult and impractical, and iii) obtaining optimal path given a nonlinear utility function is a NP-hard problem. Consequently, a heuristic two-stage strategy which identifies multiple routes and then select the near-optimal path may be effective and practical. As the first stage, we utilize the relaxation based pruning technique based on an entropy model to recognize and discard most of the nondominated paths that do not reflect the drivers' preference and/or the context-dependency ofthe preference. In addition, to make sure that paths identified are dissimilar in terms of links used, the number of shared links between routes is limited. We test the proposed algorithms in a large real-life traffic network and show that the algorithms reduce CPU time significantly compared with conventional multi-criteria shortest path algorithms while the attributes of the routes identified reflect drivers' preferences and generic route choice behaviors well.
영어 초록
In route guidance systems fastest-path routing has typically been adopted because of its simplicity. However, empirical studies on route choice behavior have shown that drivers use numerous criteria in choosing a route. The objective of this study is to develop computationally efficient algorithms for identifying a manageable subset of the nondominated (i.e. Pareto optimal) paths for real-time vehicle routing which reflect the drivers' preferences and route choice behaviors. We propose two pruning algorithms that reduce the search area based on a context-dependent linear utility function and thus reduce the computation time. The basic notion of the proposed approach is that i) enumerating all nondominated paths is computationally too expensive, ii) obtaining a stable mathematical representation of the drivers' utility function is theoretically difficult and impractical, and iii) obtaining optimal path given a nonlinear utility function is a NP-hard problem. Consequently, a heuristic two-stage strategy which identifies multiple routes and then select the near-optimal path may be effective and practical. As the first stage, we utilize the relaxation based pruning technique based on an entropy model to recognize and discard most of the nondominated paths that do not reflect the drivers' preference and/or the context-dependency ofthe preference. In addition, to make sure that paths identified are dissimilar in terms of links used, the number of shared links between routes is limited. We test the proposed algorithms in a large real-life traffic network and show that the algorithms reduce CPU time significantly compared with conventional multi-criteria shortest path algorithms while the attributes of the routes identified reflect drivers' preferences and generic route choice behaviors well.
참고 자료
없음