具時間窗限制提送貨問題之研究

Abstract

貨運業者為滿足客戶需求，又面臨同業競爭壓力，以在分秒必爭之微利時代從中勝出。如何提供此一迅捷、確實之貨運品質以滿足客戶之貨運需求，即為各貨運公司之核心價值所在，其中最為關鍵的部份乃為貨車提送貨路徑選擇。良好的路徑規劃可減少諸如車輛油耗、司機工作時間等因素所反應之營運成本，亦可增加公司整體貨運量與貨運時間之彈性，以滿足多元化的貨運需求，並進一步提高公司聲譽和顧客忠誠度，對於貨運公司之永續經營乃極為重要之因素。本研究之目的在滿足所有貨運需求、允許提送貨時間窗、貨物材積等限制因素下產生一組最小成本為目標之車輛繞行路徑。同時藉由路徑規劃作業之自動化，提供較佳車輛繞行路徑，降低人工調度負擔。

本研究採用基因演算法，求解具時間窗限制提送貨問題。目標為最小化所有車輛之總旅行距離，以及違反時窗限制的懲罰成本。本研究設計十個大小不同的演算範例進行驗證，同時針對各項因子，如人口數、車輛數、車容量、突變率、突變比例、懲罰乘數以及停止條件為連續演化固定世代，對於求解品質及速度之影響，故針對以上因子進行一系列之敏感度分析。經研究結果可知，本研究可在滿足允許執行時間窗、提送貨任務配對、提送貨優先次序、司機下班時間與車輛載重容量等提送貨特性條件下進行求解，並可適用於各種不同規模的問題。

Under the highly competitive circumstance, providing good quality service is the core value of all freight transportation companies. An effective routing plan for pickup and delivery is the most important part contributing to reducing fuel consumption and operation costs. The purpose of this research is proposing an efficient solution algorithm for a real world pickup and delivery problem with time window constraints while minimizing the total vehicles used.

This research adopts Genetic Algorithm for solving the pickup and delivery problem with time windows constraints. The goal is minimizing the total traveling distance and the degree of violating time windows constraints. Ten testing cases with different sizes are generated for testing purpose. We also conduct sensitivity analysis for various factors, such as population, vehicle numbers, vehicle capacity, mutation rate, mutation percentage, penalty weights, and stopping rules. Our testing results show that the proposed algorithm is efficient and sound.