应用蚁群最佳化演算法求解航空快递员途程问题

【类型】学位论文

【作者】蓝唯诚 

【关键词】 蚁群最佳化 航空快递员 旅行推销员问题 多停点区位途程问题

【摘要】陸運取件與遞送乃航空快遞業重要之核心作業，而正確的路線規劃方針不僅可擴大快遞員之服務範圍，公司亦可藉此節省人力資源及成本。面對與日俱增的勞動及燃料成本，有效率的途程規劃對航空快遞業是不可或缺的。本研究針對物流特性之不同，將郊區之快遞員途程問題視為旅行推銷員問題(traveling salesman problem, TSP)；而將都市之快遞員途程問題視為多停點區位途程問題(multi-stop location-routing problem, MSLRP)。針對郊區之快遞員途程問題，快遞員必須以最短行車路線行經所有顧客點一次，以滿足配送與取件要求。其中送件顧客點位置在路線規劃前已知，而取件需求之顧客於快遞員配送途程中隨機出現。本研究提出逐步蟻群最佳化(stepwise-ACO, SACO) 及最低成本插入式逐步蟻群最佳化(cheapest insertion stepwise-ACO, CISACO)兩種求解方法，並以三種不同型態的取件要求進行實驗。測試結果顯示在1-點更新規則下CISACO法優於SACO法，且兩者皆較傳統之最低成本插入法(cheapest insertion, CI)更能節省總行車距離。文中亦針對累積n-取件點始更新路線進行測試，結果顯示部分n-點更新規則可進一步改善1-點更新規則之最短路徑，CISACO法求得之結果均不劣於SACO法，且兩者皆遠優於CI法。針對都市之快遞員途程問題，快遞員必須以最低成本尋找適當的停車位置，並以徒步方式服務至附近顧客端。因問題之複雜程度較高，此處僅針對送件之顧客點進行路線求解，而不考慮隨機出現之取件需求。本研究提出序列(sequential)及精煉(refined)兩種求解方法。由序列法可獲得初步的停車位置及顧客點指派，並決定徒步及車輛之路線規劃，再由精煉法進一步改善途程效率。由實驗結果顯示停車點個數及總行車距離皆伴隨徒步門檻增大而減少；而總步行距離隨著徒步門檻增大而增加。針對較大的徒步門檻，精煉法更能有效降低序列法求解之總配送成本及時間；本文亦針對三種顧客分佈型態，探討對求解效果之影響。為提昇作業效率並降低公司成本，建議航空快遞業可將本研究提出之途程規劃方法應用於快遞員之日常取件與遞送流程，並將演算法求解之最佳途程規劃視為執行方針，用以替代快遞員或管理人員主觀之個人經驗。

【学位名称】硕士

【学位授予单位】元智大学

【学位授予年度】2016

【导师姓名】丁庆荣

【读秀链接】读秀链接