動態撥召公車問題等待策略之研究

Abstract

運輸是供應鏈管理配送貨物不可或缺的一環。尤其在競爭激烈的社會裡，即時及門運輸(door-to-door transportation)需求的服務品質變得愈來愈重視，如何能提供有效完善的配送服務也是未來重要的課題之一。撥召公車具有及門運送的特性，乘客可指定搭乘地點與到達目的地，在指定時間內車輛完成接載與配送的服務。撥召公車問題分為靜態問題與動態問題。靜態問題為派遣中心在車輛出發前接收乘客之起迄需求點及按照其目的選擇指定搭乘時間或到達時間，當發車後即不再接收新的即時需求。動態問題則考慮在營運期間內可隨時接收派車需求，即時需求出現時現有車輛可允許在不違反已排定之服務點前提下服務新需求點。本研究以最少營運車輛數及最短總旅行距離為目標考慮不同動態度求解動態撥召公車問題。 動態撥召公車問題可透過兩部分求解：路線構建及排程建立。路線構建部份在決定各服務點的先後順序，本研究針對靜態問題先使用最省插入法，再透過1-0交換法改善路線服務順序；針對動態問題則因應車輛即時的位置透過即時最省插入法插入動態需求。排班建立部分則在決定各車輛到達與離開各服務點之時間，主要使用三種等待策略：優先行駛策略(DF)、優先等待策略(WF)及動態等待策略(DW)。 本研究以兩個層面之模擬方法分析動態撥召公車問題，第一部分為以固定總需求數下調整動態度以比較三種等待策略之績效表現。可發現在求解動態問題上DF策略比WF策略需要較少車輛數但較長總旅行距離。本研究提出之DW策略則能求解比DF策略較短之總旅行距離，使得DW策略比DF策略及WF策略同時較少營運車輛數及較短總旅行距離之效果。第二部分為固定即時需求下，額外成本與已知需求數間的關係。從中發現當已知需求數愈來愈多時，需要服務同數量之動態需求數呈遞減狀況，符合一般經濟規模的原理。但在第一部分中我們卻發現在大約60%以後的動態問題所需要之營運車輛數及總旅行距離有下降的趨勢，甚至在大型問題上此情況更為明顯，似乎與現實狀況下對“資訊愈早取得愈有價值”之一般認知有所不符，本研究稱此現象為直覺之相反“counter-intuitive”，值得作後續之探討。

The Dial-A-Ride problem (DARP) is a problem of providing demand responsive transport that delivers passengers from their specified origins to destinations with desired time windows. To keep a level of services, the operator should deliver the passengers subject to maximum riding time and waiting time constraints. Such problem is similar to the pick-up and delivery problem with time windows in the theme of supply chain management, but considering passenger transportation rather than goods transportation. In a Static Dial-A-Ride Problem, the operator accepts requests before the day of operation, while the Dynamic Dial-A-Ride Problem (DDARP) allows receiving requests throughout the operating period. This study focused on solving DDARP, under different degree of dynamism (dod), with minimum operating vehicles and minimum total travel distance.

There are two sub-problems solving DDARP: routing and scheduling is a sub-problem for route constructions which aims to plan the vehicle routes and stops in visiting the requests with several objectives. The Cheapest Insertion (CI) method is used to construct initial routes. The initial routes can later be improved by exchange method. Scheduling is a sub-problem for designing the arrival and departure time for each stop along the routes. It aims to insert as many real-time requests as possible in each vehicle during the day of operation. Three different strategies, namely, Drive First (DF), Wait First (WF) and Dynamic Wait (DW) are described in this study.

A set of simulation experiments were designed to evaluate the performance of the three waiting strategies under different dod. Compared to the results of DF strategy and WF strategy, the DW strategy provides a better solution with requiring less operating vehicles and shorter travel distance. We found that the requirement of extra operating costs serving a fixed number of dynamic requests decreased as more requests were known in-advance. This observation follows the principle of “economy of scale”. An interesting finding in the study was that the system may require less operating vehicles and total travel distance in a fully dynamic environment (dod = 100%) as compared to a highly dynamic problem (say dod = 60%), under a fixed number of total requests. This is in opposition to our intuition that more information can bring the system to a lower cost, and we name this case a “counter-intuitive” observation.