配送倉儲選位問題之模式分析與解算法之研究

A Study on the Warehouse Location Problem

呂俊潔(Chun-Chieh Lu)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(2006年)

https://doi.org/10.6838/YZU.2006.00116

摘要

本研究包含兩個部分，第一個部分根據倉儲選位問題的兩個特性：有無容量限制以及配送是否可分割來探討成本之差異。在第二個部分提出兩個方法：模擬退火法和變動鄰域搜尋法，來求解有容量限制配送可分割之倉儲選位問題，並且根據OR Library的標竿測試例題來討論兩者之成效。
倉儲選位問題之目標為找出一組使總成本為最小之配送倉儲，總成本包含配送倉儲之建構成本以及運輸成本。倉儲選位問題可以根據配送倉儲是否有分擔其他倉儲的配送量而進一步地分類成有容量限制或無容量限制問題。同樣地，倉儲選位問題在每一位顧客只能由單一倉儲配送時，被稱為不可分割問題；否則稱為可分割問題。本研究透過簡單的證明得知無容量限制倉儲選位問題之最佳解會發生在配送不可分割的情形，證明的方式為使用LINGO軟體求解OR Library的標竿測試題而來，從這項證明的結果中可以清楚得知無容量限制倉儲選位問題在配送可分割及配送不可分割倉儲選位問題方面的成本為最小，實驗中也指出配送是否可分割問題兩者間成本的差異並不大。
本研究在提出的模擬退火演算法以及變動鄰域搜尋法中使用三種產生鄰近解的方式：一個交換一個、增加一個及減少一個配送倉儲；並使用數個移動策略來找尋可行解：隨機選取、最大未使用量、最大未使用率及最大單位成本率，成本率計算方式為建構成本加上配送之運輸成本，其總和成本除以實際配送量而來。實驗透過使用OR Library的標竿測試題的結果發現在兩種演算法中：隨機選取及最大單位成本率在平均解算數量下，求解品質上皆優於其他三者，但是解算時間較差。

關鍵字

倉儲選位 ； 運輸單體法 ； 模擬退火法 ； 變動鄰域搜尋法

並列摘要

The study consists of two parts. In the first part, we explore the cost difference due to two attributes of the warehouse location problem (WLP) – capacitated and uncapacitated, single source and multi-source. In the second part, we propose two methods for solving the multi-source capacitated warehouse location problem (MS-CWLP): Simulated annealing (SA) and Variable neighborhood search (VNS) algorithm, and discuss their performance using the benchmark instances of OR Library.
In the WLP, the cost to be considered contains warehouse construction cost and transportation cost, and the objective is to choose a set of warehouses such that the total cost is the minimum. The WLP can be further classified into capacitated and uncapacitated according to whether capacity is imposed on the warehouses or not. Likewise, a WLP is called single-source if each customer’s demand must be supplied by exactly one warehouse; otherwise, the WLP is called multi-source. A simple proof for the existence of a single-source optimal solution to the uncapacitated WLP is presented. Meanwhile, an experiment is conducted using LINGO software to solve the benchmark instances of the OR Library. It is clear that the uncapacitated-WLP has the least cost than the MS-WLP and the single-source WLP. Our experiments indicate that there is little cost difference in terms of percentage between the MS-WLP and the single-source WLP.
Three types of neighborhood are used for the proposed SA and VNS: one for one exchange, increase by one, and decrease by one. Several solution-search moving strategies are considered in the SA and VNS: random selection, the maximum unused quantity, the maximum unused rate, and the maximum cost rate per unit transported. The cost rate for a warehouse is defined as the ratio of the sum of the construction cost and the total transportation cost over the total transported units from that warehouse. Our computational results using the benchmark instances of the OR Library indicate that in both algorithms, two moving strategies - the random selection and the maximum cost rate - are superior to the other three in solution quality and the average number of solutions computed to reach the best or optimal solution, but are inferior in computational time.

並列關鍵字

Capacitated warehouse location problems ； Transportation simplex method ； Simulated annealing ； Variable neighborhood search

參考文獻

張厚祺，「模擬退火應用在自動倉儲儲位規劃之研究」，元智工學院工業工程與管理研究所碩士論文，民國86年6月。

許哲榮，「多產品配送中心場址規劃與選擇」，元智工學院工業工程與管理研究所碩士論文，民國87年6月。

紅名鴻，「無容量限制下之動態需求設施區位問題研究」，元智工學院工業工程與管理研究所碩士論文，民國91年6月。

陳怡靜，「變動鄰域搜尋法於串並聯系統複置配置問題之研究」，元智工學院工業工程與管理研究所碩士論文，民國93年6月。

Avanthay, C., Hertz, A., and Zufferey, N., “A variable neighborhood search for graph coloring”, European Journal of Operational Research, Vol. 151, pp. 379-388, 2003.