The Cash-in-transit Routing Optimization Problem with Multi-type Risks

doi:10.12005/orms.2018.0087

Abstract

Abstract: Based on cash logistics industry, this paper introduces a routing optimization problem with multi-type risks. The problem is formulated as a mixed integer linear programming problem to balance transportation cost, transit risk and risk of cash in hand. A hybrid genetic algorithm adopted in this paper is a hybrid meta-heuristic combining the exploration capabilities of GA with efficient local search based improvement heuristics and diversity management mechanism. This method consists of a GA method to determine routing decision and a greedy method to determine the risk decision. The numerical studies are adopted to analyze problem characteristics and the method performance. The results show that the hybrid genetic algorithm can solve much larger problems, produce high quality solutions and strike a satisfying balance between the computing time and the solution quality.Multi-type risks link with the vehicle routing. Customer expect demand links with risk of cash in hand.

Key words: multi-type risks, vehicle routing problem, hybrid genetic algorithm, greedy method

摘要： 以人民币现金押运为研究背景,考虑了一种基于多类型风险的现金押运路线问题,以在途风险成本、库存现金风险成本以及运输成本为优化目标,建立了混合整数线性规划模型,并提出了一种基于多样化策略和改进邻域搜索的混合遗传算法,其中遗传算法对押运路线进行选择,贪心算法用来求解各类风险指标。数值实验分别对问题特性和算法性能进行了分析。实验结果表明:1)混合遗传算法能求解更大规模的问题,得到较好的解,并很好地平衡了运行时间和求解质量;2)多类型风险影响了行驶路线;3)客户的期望需求影响了库存现金风险。

关键词: 多类型风险, 车辆路径问题, 混合遗传算法, 贪心算法

CLC Number:

F253.4

XU Guo-xun, LI Yan-feng, LI Jun, YANG fang. The Cash-in-transit Routing Optimization Problem with Multi-type Risks[J]. Operations Research and Management Science, 2018, 27(4): 72-82.

徐国勋, 李妍峰, 李军. 现金押运路线问题——基于多类型的风险[J]. 运筹与管理, 2018, 27(4): 72-82.

References

[1]Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80-91.
[2]Yu V F, Jewpanya P, Redi A A N P. Open vehicle routing problem with cross-docking[J]. Computers & Industrial Engineering, 2016, 94: 6-17.
[3]Cinar D, Gakis K, Pardalos P M. A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration[J]. Expert Systems with Applications, 2016.
[4]Vidal T. Technical note: split algorithm in O(n) for the capacitated vehicle routing problem[J]. Computers & Operations Research, 2016, 69: 40-47.
[5]Defryn C, Sörensen K, Cornelissens T. The selective vehicle routing problem in a collaborative environment[J]. European Journal of Operational Research, 2016, 250(2): 400-411.
[6]李珍萍,赵菲,刘洪伟.多时间窗车辆路径问题的智能水滴算法[J].运筹与管理,2015,24(6):1-10.
[7]Partyka J G, Hall R W. On the road to service[J]. Or/ms Today, 2000.
[8]Emir A. Delivery pricing for different demand price elasticity functions[D]. University of Florida, 2002.
[9]Eksioglu B, Vural A V, Reisman A. The vehicle routing problem: a taxonomic review[J]. Computers & Industrial Engineering, 2009, 57(4): 1472-1483.
[10]Hosny M I. Investigating heuristic and meta-heuristic algorithms for solving pickup and delivery problems[D]. Cardiff University, 2010.
[11]Iori M, Riera L J. Exact algorithms for the double vehicle routing problem with multiple stacks[J]. Computers & Operations Research, 2015, 63: 83-101.
[12]Smith L, Louis E. Cash in transit armed robbery in australia[J]. Trends & Issues in Crime & Criminal Justice, 2010(397).
[13]Yan S, Wang S S, Wu M W. A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem[J]. Computers & Industrial Engineering, 2012, 63(2): 464-473.
[14]Talarico L, S?rensen K, Springael J. Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem[J]. European Journal of Operational Research, 2015, 244(2): 457-470.
[15]Krarup J. The peripatetic salesman and some related unsolved problems[M]//Combinatorial Programming: Methods and Applications. Springer Netherlands, 1995. 173-178.
[16]Calvo R W, Cordone R. A heuristic approach to the overnight security service problem[J]. Computers & Operations Research, 2003, 30(9): 1269-1287.
[17]Michallet J, Prins C, Amodeo L, et al. Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J]. Computers & Operations Research, 2014, 41(41): 196-207.
[18]Wu M. Cash-transportation truck scheduling and planning of security company[D]. Msc thesis, National Central University, Taiwan, 2010.
[19]Chang Y H. Cash pick-up and delivery vehicle routing/scheduling under stochastic travel times[D]. Msc thesis, National Central University, Taiwan, 2011.
[20]Boonsam P, Suthikarnnarunai N, Chitphaiboon W. Assignment problem and vehicle routing problem for an improvement of cash distribution[C]. Proceedings of the World Congress on Engineering and Computer Science, 2011, 2: 1160-1164.
[21]Anbuudayasankar S P, Ganesh K, Koh S C L, et al. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls[J]. Expert Systems with Applications, 2012, 39(3): 2296-2305.
[22]Russo F, Rindone C. Planning in road evacuation: classification of exogenous activities[C]//17th International Conference on Urban Transport and the Environment, 2011.
[23]Bennett G F. Guidelines for chemical transportation safety, security and risk management2nd ed. 2008Center for Chemical Process Safety, AIChE, Wiley & SonHoboken, NJ978-0-471-78242-1194 pp. plus CD-ROM, Price: US $125.00[J]. Journal of Hazardous Materials, 2009, 166(2): 1568.
[24]Li Y, Szeto W Y, Long J, et al. A multiple type bike repositioning problem[J]. Transportation Research Part B Methodological, 2016, 90: 263-278.
[25]Coelho L C, Cordeau J F, Laporte G. Heuristics for dynamic and stochastic inventory-routing[J]. Computers & Operations Research, 2014, 52: 55-67.
[26]Gendreau M, Laporte G, Semet F. A tabu search heuristic for the undirected selective travelling salesman problem[J]. European Journal of Operational Research, 1998, 106(2): 539-545.
[27]Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31(12): 1947-1964.
[28]Cordeau J F, Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem[J]. Transportation Research Part B: Methodological, 2003, 37(6): 579-594.
[29]Kirchler D, Calvo R W. A granular tabu search algorithm for the dial-a-ride problem[J]. Transportation Research Part B: Methodological, 2013, 56: 120-135.
[30]Paquette J, Cordeau J F, Laporte G, et al. Combining multicriteria analysis and tabu search for dial-a-ride problems[J]. Transportation Research Part B: Methodological, 2013, 52: 1-16.
[31]Nanry W P, Barnes J W. Solving the pickup and delivery problem with time windows using reactive tabu search[J]. Transportation Research Part B: Methodological, 2000, 34(2): 107-121.
[32]Vidal T, Crainic T G, Gendreau M, et al. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems[J]. Operations Research, 2012, 60(3): 611-624.
[33]Vidal T, Crainic T G, Gendreau M, et al. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows[J]. Computers & Operations Research, 2013, 40(40): 475-489.
[34]Vidal T, Crainic T G, Gendreau M, et al. A unified solution framework for multi-attribute vehicle routing problems[J]. European Journal of Operational Research, 2014, 234(3): 658-673.
[35]Cherkesly M, Desaulniers G, Laporte G. A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading[J]. Computers & Operations Research, 2015, 62(C): 23-35.
[36]Padberg M, Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems[J]. SIAM review, 1991, 33(1): 60-100.
[37]Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management science, 1994, 40(10): 1276-1290.