以螞蟻演算法解決同時收送的物流路徑規劃問題

Ant Colony Optimization Solutions for Logistic Route Planning with Pick-up and Delivery

呂學展(Eric Hsueh-Chan Lu) ； 楊雅雯(Ya-Wen Yang)

《國土測繪與空間資訊》 4卷2期 (2016/07) Pp. 139-157

摘要

近年來，由於網路技術的進步與行動裝置的普及，人們可以隨時隨地的透過網路商店瀏覽與購買商品，同時，網路商店帶來的便利性造成了人們購物習慣的改變。這種購物習慣產生了大量的貨物需要藉由物流業者配送至人們手上，進而帶動了物流產業的發展，與物流相關的研究議題越來越受到重視。其中物流路徑規劃問題是相關議題中的重點之一，雖然過去的研究已經探討許多經典的路徑規劃問題，但卻沒有考慮到物流路徑規劃中的實際限制，使得這些長期探討的問題卻又無法直接應用到現實的物流路徑規劃問題中。為了將研究更貼近生活，規劃中需要考慮車子容量、來自客戶的各種需求、與現實中的道路情形等。在此篇研究中，我們基於螞蟻演算法，提出改良式物流路徑規畫方案，套用在更貼近現實的同時考慮收送之物流規劃問題中，以減少貨車總行駛成本。接著比對以貨物之間距離為導向的規劃，和以平均貨車行駛距離為導向的規劃，哪一種螞蟻演算法概念較為合適。為了提出完整的實驗評估，我們從嘉里大榮貨運取得真實物流資料，先針對這兩種概念進行參數調整，接著根據此實驗結果，進行探索機率的參數調整，調整完畢後進行測試，比較這兩種方法之間是否會因為貨物數量的多寡和貨車容量的大小而有所不同，實驗結果顯示，我們所提出的改良式螞蟻演算法解決方案，確實能夠降低物流中的總行駛成本。

關鍵字

物流 ； 空間定位服務 ； 資料探勘 ； 路徑規劃

並列摘要

Recently, with the development of wireless communication and popularity of mobile smart devices, there are something different in our life. People normally buy things online, because it is very convenient to buy anything anytime anywhere. The change of consuming behaviors produce raising economic profit and there are a lot of products need to be transported by logistic companies. Meanwhile, the researches on logistics have attracted attention. Among these researches, one popular topic is logistic route planning. Although researchers have studied this issue for a long term, considering the limitation of logistic in reality, this solution cannot directly solve real problem. In reality, we need to consider capacity of vehicle, requests from customers, etc. In this paper, we want to know classical Ant Colony Optimization (ACO) is it can efficiently improve routing result. To compare with it, we use a concept of modified ACO in VRP. We use this concept and apply it to logistic problem. After experiment, we find that modified concept is not suitable in logistic routing problem.

並列關鍵字

Data Mining ； Location-Based Service ； Logistic ； Route Planning

參考文獻

Albayraka, M.,Allahverdib, N.(2011).Development A New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms.Expert Systems with Applications.38(3),1313-1320.

Asadpour, A.,Goemans, M.,Madry, A.,Gharan, S. O.,Saberi, A.(2010).An O(logn/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.SODA.(SODA).

Belloso, J.,Juan, A. A.,Faulin, J.,Serrano, A.(2015).Using Multi-Start Biased Randomization of Heuristics to Solve The Vehicle Routing Problem with Clustered Backhauls.Lecture Notes in Management Science.7,15-20.

Bortfeldta, B.,Hahnb, T.,Mannela, D.,Monch, L.(2015).Hybrid Algorithms for The Vehicle Routing Problem with Clustered Backhauls and 3D Loading Constraints.European Journal of Operational Research.243(1),82-96.

Chen, R. M.,Hsieh, F.-R.,Wu, D. S.(2012).Heuristics based Ant Colony Optimization for Vehicle Routing Problem.ICIEA.(ICIEA).