基于作业负荷均衡的金融押运车辆调度问题

doi:10.12066/j.issn.1007-2861.1993

摘要/Abstract

摘要：

针对金融押运成本高且各押运线路工作量不均衡等问题, 提出一个综合优化目标和解决方案, 建立以押运成本最优化和押运线路工作量均衡为目标的多目标优化模型. 选取上海保安押运有限公司在青浦区的早送晚接业务数据建立实际算例, 以 Solomon 插入节约算法获取初始解, 并采用基于模拟退火算法的 LocalSolver 和带精英保留策略的非支配排序遗传算法 (non-dominated sorting genetic algorithm-Ⅱ, NSGA-Ⅱ)对问题分别进行优化求解. 实验设计考虑车辆恒速和早晚高峰影响车辆行驶速度的不同情况, 比较不同算法的结果, 以获取资源合理配置的解决方案.

关键词: 金融押运, 模拟退火算法, 遗传算法, 工作量均衡, 多目标优化

Abstract:

This paper explores the vehicle routing problem for cash transportation by taking into account the workloads and costs. A real case in Shanghai is studied, and various factors, e.g. traffic jams are considered. In order to obtain a satisfactory solution, this paper has tested with the Solomon insertion heuristic algorithm, the neighborhood search heuristic, and the non-dominated sorting genetic algorithm-Ⅱ (NSGA-Ⅱ). Simulation studies indicate that the neighborhood search heuristic outperforms the Solomon algorithm and NSGA-Ⅱ when the speed of vehicles keeps changing under undesirable traffic conditions. But for instances with good traffic conditions, the NSGA-Ⅱ generates a better result. Other aspects of the problem are also discussed for the purpose of offering suggestions and practicable method for decision making of practitioners and researchers.

Key words: cash transportation, simulated annealing algorithm, genetic algorithm, workload balance, multi-objective optimization

中图分类号:

F252

李明琨, 柏高帅, 蒋欣颖. 基于作业负荷均衡的金融押运车辆调度问题[J]. 上海大学学报(自然科学版), 2019, 25(5): 836-850.

Mingkun LI, Gaoshuai BAI, Xinying JIANG. A modeling and solution method for cash transportation vehicle routing from the perspective of workload balancing[J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(5): 836-850.

图/表 11

图1

表1

表2

图2

图3

图4

表3

图5

图6

图7

图8

参考文献 28

[1]	Dantzig G, Ramser J . The truck dispatching problem[J]. Management Science, 1959,6(1):80-91.
[2]	Yan S Y, Wang S S, Wu M W . A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem[J]. Computers and Industrial Engineering, 2012,63(2):464-473.
[3]	Archetti C, Doerner K F, Tricoire F . A heuristic algorithm for the free newspaper delivery problem[J]. European Journal of Operational Research, 2013,230(2):245-257.
[4]	Kim B I, Kim S, Park J . A school bus scheduling problem[J]. European Journal of Operational Research, 2012,218(2):577-585.
[5]	Wy J, Kim B I, Kim S . The rollon-rolloff waste collection vehicle routing problem with time windows[J]. European Journal of Operational Research, 2013,224(3):466-476.
[6]	Huang X, Song L . An emergency logistics distribution routing model for unexpected events[J]. Annals of Operations Research, 2018,269(1/2):223-239.
[7]	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.
[8]	Talarico L, Springael J Sörensen K , et al. A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem[J]. Computers and Operations Research, 2017,78:547-556.
[9]	陈子侠, 蒋长兵 . 杭烟物流送货线路的划分模式与算法研究[J]. 系统工程理论与实践, 2004,24(3):46-51.
[10]	刘晓翀, 戴敏, 郑刚 , 等. 运钞车车辆路径规划策略[J]. 计算机应用, 2011,31(4):1121-1124. doi: 10.3724/SP.J.1087.2011.01121
[11]	孙有望, 宋华骏 . 以均衡为目标的车辆调度问题研究[J]. 物流科技, 2010,33(6):22-25.
[12]	贺政纲, 刘沙 . 考虑均衡负载的车辆路径问题及算法设计[J]. 工业工程, 2015(4):140-145.
[13]	刘恒宇, 汝宜红 . 考虑交通拥堵及工作量平衡性的一致性车辆路径问题[J]. 西南交通大学学报, 2016,51(5):931-937.
[14]	Karp R M . Reducibility among combinatorial problems[M]// Miller R E, Thatcher J W, Bohlinger J D. Complexity of computer computations. Boston: Springer, 1972: 85-103.
[15]	Savelsbergh M . Local search in routing problems with time windows[J]. Annals Operations Research, 1985,4(1):285-305.
[16]	Solomon M M . On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints[J]. Networks, 1986,16(2):161-174.
[17]	Solomon M . Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987,35(2):254-265.
[18]	Alabas-Uslu C . A self-tuning heuristic for a multi-objective vehicle routing problem[J]. Journal of the Operational Research Society, 2008,59(7):988-996.
[19]	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.
[20]	Berbotto L, García S, Nogales F J . A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem[J]. Annals of Operations Research, 2014,222(1):153-173.
[21]	Yao B, Yu B, Hu P , et al. An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot[J]. Annals of Operations Research, 2016,242(2):303-320.
[22]	Mavrovouniotis M, Yang S . Ant algorithms with immigrants schemes for the dynamic vehicle routing problem[J]. Information Sciences, 2015,294:456-477.
[23]	Srinivas N, Deb K . Multi-objective function optimization using non-dominated sorting genetic algorithms[J]. Evolutionary Computation, 1995,2(3):221-248.
[24]	Knowles J D, Corne D W . Approximating the non-dominated front using the pareto archived evolution strategy[J]. Evolutionary Computation, 2000,8(2):149-172.
[25]	Zitzler E, Thiele L . Multi-objective evolutionary algorithms: a comparative case study and the strength pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999,3(4):257-271.
[26]	Deb K, Pratap A, Agarwal S , et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197.
[27]	Tan K C, Lee L H, Ou K . Artificial intelligence heuristics in solving vehicle routing problems with time window constraints[J]. Engineering Applications of Artificial Intelligence, 2001,14(6):825-837.
[28]	Osman I H . Metastrategy simulated annealing and Tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research, 1993,41(4):421-451.