以群蟻演算法求解動態車輛途程規劃

《以群蟻演算法求解動態車輛途程規劃》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、以群蟻演算法求解動態車輛途程規劃王順生1,李國村21工業工程與管理系朝陽科技大學台中縣霧峰鄉吉峰東路168號sswang@cyut.edu.tw2工業工程與管理系朝陽科技大學台中縣霧峰鄉吉峰東路168號摘要：面對全球經濟競爭，產業必須提高品質、降低成本以提升競爭力，物流成為全球企業關注的焦點，降低運輸成本更是一大課題。本研究針對顧客需求以群蟻演算法來進行車輛途程規劃。另外，藉由定位系統收到的即時交通資訊，應用K條最短路徑演算法來選擇替代性道路，因此能獲得動態資訊下的最佳路線，以反應真實的交通狀況。關鍵詞：物

2、流管理、群蟻演算法、動態資訊、車輛途程規劃1.前言近年來由於世界經濟的全球化、貿易的自由化、產品生命週期的縮短、客戶要求服務水準的提升等因素，物流(或稱運籌，Logistics)成為全球企業關注的焦點，善用物流以提高顧客服務的水準，並滿足顧客的需求已成為企業強化競爭優勢的重要策略。物流的範圍相當廣泛，與物流相關的活動包括裝卸、包裝、保管、運送、資訊及流通加工等作業，這些活動中以運送的不確定性因素最高。一般的運送方式及車輛的派遣都是場站（Depot）接下訂單或貨物後，由司機自行決定送貨、收貨的途程路線，在這種

3、情況下司機可能因為路線不熟、安排不洽當等因素而使得途程的時間增加，若能夠在派車前將途程路線規劃好，則可以減少許多不必要的時間浪費。近年來商用車輛營運系統成為智慧型運輸系統發展以來重要的課題之一，其中商車營運系統係利用先進交通管理系統（AdvancedTrafficManagementSystems,ATMS）、先進旅行者資訊系統（AdvancedTravelerInformationSystems,ATIS）與先進車輛控制及安全系統（AdvancedVehicleControlandSafetySystem

4、,AVCSS）之技術將「路、車系統智慧化」且應用於商用運輸上；司機可透過車輛上的全球定位系統（GlobalPositioningSystem,GPS），進行監控營運車輛的位置，並根據即時交通路網狀況來改善車輛的運送路線，以減少途程、載貨、送貨所需的時間及成本，並提昇顧客貨物運送的服務水準，因此動態車輛途程規劃問題（DynamicVehicleRoutingProblem,DVRP）逐漸的受到重視。國內外探討車輛途程規劃問題（VehicleRoutingProblem,VRP）的文獻，前提假設大多以靜態模式來

5、計算現有路線規劃的最佳路線，這些演算法也只能被應用在顧客需求量、時間變數（車輛運送時間、時間窗）為明確數值時，對於現實生活中的時間變數不確定的情形下較不能適用，因此無法適時反應道路的即時車流狀況。該問題屬於指數型困難問題，若以數學規劃方式進行求解時，其問題規模變大，需要較長的運算求解時間，無法保證在可接受的時間內求出最佳解，若車輛途程規劃再加上時間窗限制，將使困難的問題更加複雜化，故許多啟發式演算法被應用於解決類似的問題。本研究探討車輛自配送中心運送貨物至各需求點時途程路線的問題。由於車輛在運送貨物時會因為

6、天氣、道路與即時資訊等狀況，而使車輛途程的路線改變，因此必須在獲得即時交通資訊下重新規劃新的車輛途程路線，以保持應有的貨物運送水準。本研究主要以群蟻最佳化演算法（AntColonyOptimization,ACO）求解即時資訊下的車輛途程路線問題。2.文獻探討車輛途程規劃的研究領域非常廣泛，無論是在實體的物流配送業、快遞服務業，或是學術上的工業工程或交通運輸領域，其研究與應用都相當多。車輛途程規劃指的是一個物流中心的營運車輛從場站出發，運送貨物到已知需求的顧客處，行駛於各路線的車輛必須從場站出發，且最後必須

7、回到場站。每一個顧客只能被服務一次，任一條路線的顧客群的需求量的總和不得超過該路線車輛的容量限制。基本上車輛途程規劃的目的是求所有路線的總距離最短或總運送成本最低。傳統的車輛途程規劃是被歸類為作業研究領域中的整數線性規劃（IntegerLinearProgramming）。Danzig和Ramser將之稱為「旅行推銷員問題」（TravelingSalesmanProblem,TSP），但後來逐漸以車輛途程規劃稱呼較為普遍(Laporte&Osman,1995)。2.1求解車輛途程規劃的方法Bodin等學者將

8、求解車輛途程規劃的方法分為七類(Bodin,Golden,AssadandBall,1983)：1、先分區再排路徑（ClusterFirst-RouteSecond）：先依據距離或時間窗限制等關鍵因素將所有的顧客予以分區，再從各分區中找出成本最低的車輛途程。2、先排路徑再分區（RouteFirst-ClusterSecond）：暫不考慮車容量限制，先對所有顧客求出最佳途程，再依實際限制予以分割成數個單獨的路線。3