週期性車輛排程問題之研究

Investigations for Period Vehicle Routing Problem

涂慧敏(Huei-Min Tu)

指導教授 ： 邱素文

大同大學/經營設計學院/資訊經營學系所/碩士(2004年)

摘要

週期性車輛排程問題是一個為服務所有的顧客而設計車輛路徑的分配問題，並且指定的日期須在一個短的設定區間內,稱為週期。此目的是希望能將此週期間的配送成本最小化。因此如何能以非常短的時間求解出一個可接受的解則是一個非常重要的課題。
在第一階段，我們研究一個方法來為每位顧客選擇配送日期的組合。首先，我們先排列所有顧客之順序，接著我們按照此順序來指派顧客之服務組合。根據週期性車輛排程問題的目標，我們使用了旅行推銷員問題中的最近插入法來計算所指派顧客之成本，然後選擇增加最少的成本並可行的運送組合。在第二階段，針對每日車輛路徑問題，我們使用Sequential Savings和Modified Sweep演算法產生每日的初始車輛路徑，並且使用2-optimal方法來改善每日的路徑。
為了測試及驗證我們在所提出的方法，另外，我們在第一階段也使用 “Lindo What’s Best” 來求解Chao et al. (1995) 所提出的整數規劃法求出顧客配送日期的組合，在第二階段使用Sequential Savings和Modified Sweep演算法求解每日的初始車輛路徑，並以Chao et al. (1995) 所提出one-point movement方法及2-optimal來改善每日的初始路徑。我們測試了5題國際標竿題庫和2題隨機產生的例題，根據實驗的結果,我們可以發現我們所提出的方法是較佳並可行的,且都可在4秒內求算出可行解。我們也和Christofides and Beasley (1984)， Tan and Beasley (1984)， and Rusell and Gribbin (1991),比較5題國際標竿題庫的配送成本，平均誤差分別為10%、5%c 和 13%；而和目前已知的最佳解比較，平均誤差則為16%。

關鍵字

2-optimal heuristic ； One-Point Movement ； 掃瞄法 ； 車輛排程問題 ； 週期性車輛排程問題 ； 節省法

並列摘要

The Period Vehicle Routing Problem (PVRP) is a distribution problem about designing vehicle routes to serve those customers, which are assigned to that day over a short planning period. The objective is to minimize the cost of distribution over the period. How to determine the acceptable solutions in very short time is an important issue.
In the first phase we investigated one method to determine a choice of delivery day combinations for customers. First, we formed the ordering of the customers, and then we assigned each customer along the order. According to the objective of PVRP, we used Nearest Insertion of Traveling Salesman Problem (TSP) to evaluate the cost of assigning the customer, and chose the least increase cost and feasible delivery day combination. In the second phase, we adopted Savings and Modified Sweep for the daily vehicle routing problem (VRP), and then used 2-optimal approach to improve the daily routes. In order to test and verify the method we proposed in the first phase, we employed an integer program in Chao et al. (1995) for determining customer delivery day combinations; in the second phase, solved the daily VRP using Savings and Modified Sweep and the daily routes were improved by modified one-point movement plus 2-optimal interchange. And we used these two different methods in the first phase, and used the same method in the second phase to test five benchmarks and two randomly generated instances. According to the experimental results, we can find the method in the first phase we proposed is the better and feasible, and the computation time is all within 4 seconds. We also compared the delivery cost of the five benchmarks with Christofides and Beasley (1984), Tan and Beasley (1984), Rusell and Gribbin (1991), and the best-known solutions, and found the average deviations are respectively about 10%, 5%, 13% and 16%.

並列關鍵字

2-optimal heuristic ； One-Point Movement ； Period Vehicle Routing Problem (PVRP) ； Savings algorithm ； Sweep algorithm ； Vehicle Routing Problem (VRP)

參考文獻

1. Anily, S., A Federgruen (1993), “Two-Echelon Systems with Vehicle Routing Costs and Central Inventory”, Operations Research 41, pp.37-47.

2. Bard, J. F., L. Huang, P. Jaillet, and M. Dror (1998), “A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities”, Transportation Science 32, pp.189-203.

3. Bellmore, M. and G. L. Nemhauser (1968), “The Traveling-Salesman Problem: A Survey”, Operations Research 16, pp.538-558.

4. Chao. I., B. L. Golden and E. Wasil (1995), “An improved Heuristic for the Period Vehicle Routing Problem”, Networks 26, pp.25-44.

5. Christofides, N. and J. E. Beasley (1984), “The Period Routing”, Networks 14, pp.237-256.