區位途程與易腐性商品排程之研究

A Study on Location Routing Problem and Production Scheduling for Perishable Goods

池昆霖(Kun-Lin Chih)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2006年)

摘要

摘要
易腐性商品的價值會隨著時間而遞減，為了有效的追求廠商利潤的最大化，本研究嘗試將生產排程、車輛途程兩種問題加以整合，並納入區位選擇以及時窗限制之要求，最後定式為ㄧ雙層混合整數規劃模型。本研究亦同時研提一啟發式求解演算法:上層部分先暫時固定場站位置，再求解下層問題，下層部分利用分解(decomposition)的概念將問題分解成生產排程問題與車輛途程問題；生產排程部份採用Nelder-Mead 演算法來求解，至於配送部份利用修正後的插入法(insert method)來建構初始解。由於現今低溫冷凍商品之市場佔有率日益增加，因此易腐性商品生產排程與車輛途程問題之重要性也將隨之提高，而製造工廠的設置區位，更是企業期初投資成本的ㄧ大考量，本研究在短期最佳化的情況下去求解長期的成本最小化問題，因此建構此一雙層規劃模型，為了增加本模型之實用性，建立友善之使用者界面以及提高演算法之效率，將成為未來重要之研究方向。

關鍵字

Nelder-Mead 演算 ； 易腐性商品 ； 生產排程與車輛途程問題 ； 區位選擇

並列摘要

The value of the perishable goods will decrease by the time. In order to efficiently find the maximized profit for the manufactory, we try to integrate the production scheduling, vehicle routing problem, take into the location problem, time window constrains, and finally formulate a bi-level integer programming problem. We also propose a heuristic solution algorithm, and we fixed the location of depots at the upper-level, then to solve the lower-level. At the lower-level, we use the concept of decomposition to decompose the problem as production scheduling problem and vehicle routing problem. At the part of production schedule, we use the Nelder-Mead algorithm to solve, and use the modified insert method to construct the initial solution at the part of vehicle routing. As the result of increasing of market share ratios for frozen production by the day, therefore it is more important in the production scheduling for perishable goods and vehicle routing problem. And it’s a major factor for a business to determine the location in the beginning investment cost. The study solving the minimum long-term cost problem under the condition of short-termed optimization, therefore we construct a bi-level programming modal. For increasing the practicability of the modal, it will be an important research direction to set up friendly user interface and improve the efficient of algorithm in the future.

並列關鍵字

Location ； Production Scheduling and Vehicle Routing ； Nelder-Mead Algorithm ； Perishable Commodity

參考文獻

[45] Teng J.T., and Ouyang, L.Y., (2005), “An EOQ Model for Deteriorating Items with Power-Form Stock-Dependent Demand,” Information and Management Sciences, Vol. 16, pp. 1-16.

[6] 林志鴻、陳春益、曹以明(2000)，「汽車運送業拖車調度問題求解之研究」，中華民國第五屆運輸網路研討會論文集，pp. 205-215，台中。

[10] Abad, P.L., (1996), “Optimal Pricing and Lot-sizing under Conditions of Perish Ability and Partial Backordering,” Management Science, Vol. 42, pp. 1093-1104.

[11] Andrew, L., and Fan, W., (2005), “Multi-Depot Vehicle Routing Problem：A One-Stage Approach,” IEEE Transactions on Automation Science and Engineering, Vol. 2, No. 4, pp. 397-402.

[12] Aykin, T., (1995), “The Hub Location and Routing Problem,” European Journal of Operational Research,” Vol. 83, pp. 200-219.