在不同運作模式下具容量限制的車輛途程問題之比較研究

A Comparative Study of Different Operation Models for Capacitated Vehicle Routing Problems

黃浩維(Hao-Wei Huang)

指導教授 ： 謝富雄

朝陽科技大學/資訊學院/資訊工程系/碩士(2015年)

摘要

近年來資訊科技與交通運輸的發達，物流產業已迅速的發展成為目前重要的產業之一，而在全球化的生產模式下，使得傳統的供銷體系已經無法因應。其中最重要的是涉及到尋找最佳的配送路線，因為這將會提供很大的潛力來降低成本，並且提高服務的品質。在現有的文獻中對於各種車輛途程問題（VRP）進行了研究，然而，大多數的車輛路徑問題研究了基於不同的運作模式，缺乏了具容量限制的車輛路徑問題的不同的經營模式的比較研究。而本研究主要目的是針對混和式離散型粒子群演算法進行改良[46]，使其演算法可以對於同時拾取和交付的容量限制之車輛途程問題(Capacitated Vehicle Routing Problem Simultaneous Pickup and Delivery, CVRPSPD）提升效能的表現。同時我們也對於整個物流業者的運作流程加入了「順路交付」的行為，可以達成節省運送成本、縮短運送時間和增加車輛效能。並且實現一個物流業者的模擬實驗平台，可以設定業者的相關參數和演算法的相關參數，進行模擬測試實驗將計算結果輸出提供分析。此外我們還使用Google Map API將計算結果顯示於地圖上，以利使用者更方便的用肉眼觀察出計算結果，我們最後還加入了一個目標，就是在模擬實驗平台上可以進行業者合作的實驗測試。在本論文中，我們結合了Google Map API和離散型粒子群演算法(DPSO)開發一個車輛途程演算法，並基於我們的演算法在不同的運作模式下比較各個例子的數據。

關鍵字

同時拾取和交付 ； 離散型粒子群演算法 ； 車輛途程問題 ； 運作流程

並列摘要

Logistics is the management of the flow of goods between the point of origin and the point of consumption to meet requirements of customers. Transportation is an important part of logistics as it imposes considerable cost on goods and has a significant influence on competitive advantage of a company. How to reduce the costs and improve the profit of a company is an important issue. Vehicle routing is a critical factor in reducing transportation costs. Finding optimal vehicle routes offers great potential to efficiently manage fleets, reduce costs and improve service quality. An effective scheme to manage fleets and determine vehicle routes for delivering goods is important for carriers to survive. In the existing literature, a variety of capacitated vehicle routing problems (VRP) have been studied. However, most VRP that have been studied are based on different operation models. There is a lack of a comparative study on different operation models for capacitated VRP. In this paper, we aim to develop a decision support system to compare the performance of several different operation models of VRP. The goal is to provide an effective tool to support the decisions of logistics companies. To achieve this goal, we propose an operation model, formulate an optimization problem and develop solution algorithms based on Google Maps API. In our problem formulation, we consider a set of goods to be picked up and delivered. Each goods has a source address and a destination address. The vehicles to transport the goods have limited capacities, including the maximal weight a vehicle can be carried and the maximal distance a vehicle can travel. The problem is to minimize the routes for picking up and delivering goods. The emerging Google Maps API provides a convenient package to develop an effective vehicle routing system. In this paper, we develop a vehicle routing algorithm by combining a discrete particle swarm optimization (DPSO)[46] method with Google Maps API. We compare the performance of different operation models based on our algorithms by numerical examples.

並列關鍵字

Simultaneous Pickup and Delivery ； Discrete particle swarm algorithm ； Vehicle Routing Problem ； Operational processes

參考文獻

[3] Fisher M. L. 1995,“Vehicle e Routing Network Routing, Handbooks in Operation Research and Management Science”, 8, 1-33.

[5] I. H. Osman “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem” Annals of Operations Research, vol. 41, no. 4, pp. 421-451, 1993.

[6] A. V. Breedam“Improvement heuristics for the Vehicle Routing Problem based on simulated annealing” European Journal of Operational Research, vol. 86, no. 3, pp. 480-490, 1995.

[7] T. R. Moghaddam,N. SafaeiandY. Gholipour “A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length” Applied Mathematics and Computation, vol. 176,no. 2, pp. 445-454, 2006.

[8] S.W. Lin, Z.J. Lee, K.C. YingandC.Y. Lee “Applying hybrid meta-heuristics for capacitated vehicle routing problem” Expert Systems with Applications, vol. 36, no. 2, pp. 1505-1512, 2009.