以混整數規劃求解時窗限制內單一共用財調配問題

Mathematical Programming Model for Solving the Time-Windowed Tool Relocation Problem

陳昭瑜(Chao-Yu Chen)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201801435

摘要

共用財共享系統因有需求不平準的問題，衍生出卡車繞行站點調配共用財以減少需求未滿足的問題。本研究即針對「時窗限制下單一共用財調配問題」研擬混合整數規劃求解法。期能透過數學規劃模型，求得問題的全域最佳解，協助系統營運者進行共用財調配減少需求未滿足量。在各站點共用財初始數及增減率已知下，根據繞行及調配規則逐一探討時窗內不同情境下的未滿足量的計算方式。本研究研擬本問題的單台及多台卡車混合整數線性規劃求解模型，透過此模型可求得卡車繞行各站點的最佳途程及在各站點調配的共用財數。除數學模型的研擬外並實作IBM ILOG CPLEX 的OPL(Optimization Programming Language)求解模型(程式)，並以台北市單車共享系統中10至30個站點數為測試範例。試驗時以站點共用財增減率倍增、卡車容量倍增、及以多台卡車調配等不同情境下試驗未滿足量的調配效能。範例測試結果並與啟發式演算法比較。結果顯示各情境下，混整數規劃模型的求解結果均比啟發式演算法佳或相同。研擬的數學規劃模型限制式多且複雜，實作時另撰寫程式整理求得的最佳解以驗證解的正確性及展示繞行路徑圖。

關鍵字

共享經濟 ； 共享單車系統 ； 混整數規劃法 ； 時窗限制下單一共用財調配問題

並列摘要

This paper defines mixed-integer programming model which can solve time-windowed tool relocation problem. The decision maker can make an appropriate set-tlement and the unfulfilled amount in the public tool sharing system can be reduced by mixed-integer programming model. The model calculates the unfulfilled amount in the different case because of known increasing/decreasing rate and other parameters. The model determines the routing path, pickup and delivery amount in service stations. The general constraints are too complicated, so our research aims to develop a program to verify the correctness of the solutions and draw the routing path. Our research applies the model to the bike sharing system and use it to test some examples. If the truck in the bike sharing system transfer the bikes from stations to stations, the unfulfilled amount always declines. The performance of the mixed-integer is equal or better than the per-formance of canonical method.

並列關鍵字

Sharing Economic ； Bike sharing System ； Mixed-Integer Programming ； Time-Windowed Tool Relocation Problem

參考文獻

Alvarez-Valdes, R., Belenguer, J. M., Benavent, E., Bermudez, J. D., Muñoz, F., Vercher, E., & Verdejo, F. (2016). Optimizing the level of service quality of a bike-sharing system. Omega, 62, 163-175.

Benchimol, M., Benchimol, P., Chappert, B., de la Taille, A., Laroche, F., Meunier, F., & Robinet, L. (2011). Balancing the stations of a self service “bike hire” system. RAIRO - Operations Research, 45(1), 37-61.

Cao, E., & Lai, M. (2010). The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, 37(3), 2405-2411.

Chemla, D., Meunier, F., & Wolfler Calvo, R. (2013). Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization, 10(2), 120-146.

Dell'Amico, M., Hadjicostantinou, E., Iori, M., & Novellani, S. (2014). The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega, 45, 7-19.