中文

Journal of Shanghai University >

2019 , Vol. 25 >Issue 5: 836 - 850

DOI: https://doi.org/10.12066/j.issn.1007-2861.1993

Research Paper

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

Expand
  • School of Management, Shanghai University, Shanghai 200444, China

Received date: 2017-09-11

  Online published: 2019-10-31

Fold

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

Cite this article

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, 2019 , 25(5) : 836 -850 . DOI: 10.12066/j.issn.1007-2861.1993

References

[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.
[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.
Options
Outlines

/

〈 〉