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

doi:10.12066/j.issn.1007-2861.1993

Abstract

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

CLC Number:

F252

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.

Figures/Tables 11

Fig. 1

Table 1

Table 2

Fig. 2

Fig. 3

Fig. 4

Table 3

Fig. 5

Fig. 6

Fig. 7

Fig. 8

References 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.

A modeling and solution method for cash transportation vehicle routing from the perspective of workload balancing

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 28

Related Articles 10

Recommended Articles

Metrics

Comments

[1]	YANG Wanfeng, YANG Xiao. Two-stage identification of structural damage based on incomplete static data [J]. Journal of Shanghai University（Natural Science Edition）, 2018, 24(5): 841-852.
[2]	KONG Weijian, WANG Yongfang, TONG Zilei, ZHANG Hongguang. Modeling and algorithm implementation of dietary nutrition optimization for diabetic patients [J]. Journal of Shanghai University（Natural Science Edition）, 2018, 24(4): 583-591.
[3]	HAN Yajuan, YANG Yuhang, PENG Yunfang. Rescue vehicle routing optimization considering distribution of resources in rescue points [J]. Journal of Shanghai University（Natural Science Edition）, 2018, 24(4): 655-664.
[4]	CHEN Juan, YU Yuxuan, JING Hao. Robust multi-objective signal optimization control for mixed traffic at adjacent intersection [J]. Journal of Shanghai University（Natural Science Edition）, 2018, 24(4): 665-674.
[5]	LIU Dongjun, XU Meihua, GONG Luming, XIA Chenjun. Feature fusion for front vehicle detection and implementation [J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(6): 893-.
[6]	PENG Yunfang1, GAO Ya1, XIA Beixin2. Job shop scheduling with uncertainty based on genetic algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2016, 22(6): 793-803.
[7]	WEI Xin-hua,GUO Jia-hong. Optimization of Pumping Station with Simulated Annealing and Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2009, 15(1): 32-36.
[8]	SHENG Jie;YANG Xue-xia;SUN Jiang-tao . Design of UWB Antenna Using Genetic Algorithm Optimization [J]. Journal of Shanghai University（Natural Science Edition）, 2008, 14(4): 346-348 .
[9]	WU Pin;LI Jian-dun;LIU Quan-sheng;LI Song-bei. Grid Resource Selection Strategy Based on an Adaptive Parallel Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(5): 629-633 .
[10]	ZHANG Kai yan;MO Yun hui;DENG Zhaoyi;et al . Multi object Fuzzy Reliability Optimization of Planar Gear Transmission Based on Improved Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(1): 22-27 .