時間限制條件下配銷途程問題之研究

A Study of The Vehicle Routing Problem Under Time Constraints

林志挺(Timon C. Du) ； 饒忻(Hsin Rau) ； 陳建良(James C. Chen) ； 王木坤(Mu-Quan Wang)

《中原學報》 26卷1期 (1998/02) Pp. 67-82

https://doi.org/10.6358/JCYU.199802.0067

摘要

配銷中心不同於一般產業的特性，在於其運輸成本佔公司總支出很大的部份，然而如何降低其運輸成本，成為配銷中心盈虧所在的關鍵。過去的物流中心，針對其運輸成本，只需考量路徑的安排與車輛的配置問題。而現今消費者意識抬頭，針對其所需商品，往往要求必須在一定時間範圍內送達，否則拒收或處以一定的罰金，此即為時窗限制。有了此項限制後，整個運輸成本模式變得更加複雜。
本研究針對配送車輛在路徑與顧客時窗限制的雙重考量下，提出三個啟發式演算法，以期求得理想之運輸成本。其中”等時距最小成本法”與”固定點最小成本法”都是先考慮路徑的安排，再考慮途程的規畫；其不同點在於前者以一定時問範圍內，求得具最小成本之第一顧客點的到達時間，後者則以求得相鄰兩顧客點的最小成本為目標。而”群組化最小成本法”則是先將顧客依其時窗中點分為適當的群數 1 再根據等時距最小成本法與固定點最小成本法的模擬測試，擇其較佳者當做途程的規畫方式。並以運輸成本與總距離的角度來評估其優劣。最後，以群組化最小成本法為基礎，發展一同時考量路徑與途程之”動態群組化最小成本法”，並與前面三演算法比較其績效。

關鍵字

配銷中心 ； 時窗 ； 路徑 ； 途程

並列摘要

The transportation cost is a significant portion of the operation expense toward a distribution center. Therefore, it is very important for the distribution center to reduce its transportation cost in order to increase its profit. In the past, a transportation problem focused only on the vehicle routing without taking time constraint into consideration. Today, customers often put more restricted time constraints on receiving schedule. If the time constraints are not met, either the early receiving fine or the late delivering fine will be imposed. This type of problem is called “ time window constraints “ and is more complicated than before.
First of all, this research proposes three algorithms under time constraints to reduce the transportation cost. On the list, the “minimize cost with equal-time interval” and “minimize cost with fixed points” proceed the routing analysis first, then do the scheduling. The difference between these two algorithms is that the former delays the departure time in the first customer to minimize the total cost while the latter delays the departure time in every customer to obtain the minimum cost between two customers. The third algorithm, minimum cost with grouping, groups all customer orders into clusters using the midpoint of the acceptable time interval of the customers, and the delivering time is scheduled by either previous algorithms depending on whichever generates lower costs. Then, this research proposes another algorithm, minimum cost with dynamic grouping, by considering both the distance and time window constraints. Finally, the performance comparison of these four algorithms is provided.

並列關鍵字

distribution center ； time windows ； routing ； scheduling