A Research on Distribution Problem of Electric Bicycle-sharing Batteries

doi:10.3969/j.issn.1007-7375.2019.03.007

Abstract

Abstract: The distribution plan of electric bicycle-sharing batteries has a great impact on the users' immediate experience and the interests of the company. In order to develop an optimal distribution scheme and truly get through "the last mile" of people's travel, the requirements of enterprises for the distribution cost and the users' requirements for timeliness are considered, and a model of vehicle routing problem with soft time windows with objectives of minimizing the total distribution cost and maximizing user satisfaction is established. Then the traditional genetic algorithm is improved by sweep algorithm and the crossover operator based on the cost of optimal path. Finally, an example is adopted to verify that this model and the improved algorithm are effective. And the correlation between population size, iteration number and optimal solution is found by numerical experiments.

Key words: distribution problem of electric bicycle-sharing batteries, vehicle routing problem with soft time windows, sweep algorithm, genetic algorithm

CLC Number:

TP391.9

FENG Chun, QIN Bingfang, YE Lu. A Research on Distribution Problem of Electric Bicycle-sharing Batteries[J]. Industrial Engineering Journal , 2019, 22(3): 52-56.

References

[1] 魏明, 高成修, 胡润洲. 一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法[J]. 运筹与管理, 2002, 11(3):49-54 WEI Ming, GAO Chengxiu, XIU Runzhou. The capacitated vehicle routing problem with time windows and its tabu search meta-heur istic[J]. Operations Research and Management Science, 2002, 11(3):49-54
[2] OMBUKI B, ROSS BJ, HANSHAR F. Multi-objective genetic algorithms for vehicle routing problem with time windows[J]. Applied Intelligence, 2006, 24(1):17-30
[3] 潘立军. 带时间窗车辆路径问题及其算法研究[D]. 长沙:中南大学, 2012. PAN Lijun. Vehicle routing problem with time windows and its algorithms[D]. Changsha:Central South University, 2012.
[4] 邵举平, 曹倩, 沈敏燕. 生鲜农产品配送中带时窗的VRP模型与算法[J]. 工业工程与管理, 2015, 20(1):122-128 SHAO Juping, CAO Qian, SHEN Minyan. Research on multi-objective optimization for fresh agricultural products VRP problem[J]. Industrial Engineering and Management, 2015, 20(1):122-128
[5] ZHOU H, ZHANG L, TAN Y. Adjacent domain renewal intelligent water drops algorithm based soft time window vehicle routing optimization[J]. Computer Engineering & Applications, 2015, 98(25):253-265
[6] CALVETE H I, GALE C, OLIVEROS M J, et al. A goal programming approach to vehicle routing problems with soft time windows[J]. European Journal of Operational Research, 2007, 177(3):1720-1733
[7] QURESHI A G, TANIGUCHI E, YAMADA T. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E, 2009, 45(6):960-977
[8] AZI N, GENDREAU M, POTVIN J Y. An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J]. European Journal of Operational Researeh, 2007, 178:755-766
[9] ERDO?AN G, BATTARRA M, CALVO R W. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems[J]. European Journal of Operational Research, 2015, 245(3):667-679
[10] BEHESHTI A K, HEJAZI S R. A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences, 2015, 316
[11] ROPKE S, CORDEAU J F. Branch and cut and price for the pickup and delivery problem with time windows[J]. Transportation Science, 2009, 43(3):267-286
[12] IQBAL Sumaiya, KAYKOBAD M, RAHMAN M S. Solving the multi-objective vehicle routing problem with soft time windows with the help of bees[J]. Swarm & Evolutionary Computation, 2015, 24:50-64
[13] FIGLIOZZI M A. An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows[J]. Transp. Res. Part C, 2010, 18:668-679
[14] CHIANG W C, RUSSELL R A. A metaheuristic for the vehicle-routing problem with soft time windows[J]. J. Oper. Res. Soc, 2004, 55:1298-1310
[15] XU Jiuping, YAN Fang, LI Steven. Vehicle routing optimization with soft time windows in a fuzzy random environment[J]. Transportation Researtion, 2011, 47(6):1075-1091
[16] LI P, HE J, ZHENG D, et al. Vehicle routing problem with soft time windows based on improved genetic algorithm for fruits and vegetables distribution[J]. Discrete Dynamics in Nature and Society, 2015(3):1-8
[17] MORRIS G M, GOODSELL D S, HALLIDAY R S. Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function[J]. Journal of Computational Chemistry, 2015, 19(14):1639-1662
[18] 葛显龙, 谭柏川, 吴宁谦. 基于碳交易机制的带时间窗车辆路径问题与算法研究[J]. 管理工程学报, 2018, 32(4):141-146 GE Xianlong, TAN Baichuan, WU Ningqian. Research on vehicle routing problem and algorithm with time window based on carbon trading mechanism[J]. Jonrnal of Industrial Engineering/Engineering Management, 2018, 32(4):141-146