多品种生鲜农产品的车辆路径优化
|
摘要
针对多品种生鲜农产品建立了带软时间窗约束的车辆路径优化模型,模型以配送总成本最少为目标,以生鲜农产品新鲜度阈、时间窗等为约束条件.然后,通过引入Dijkstra算法,改进交叉算子,提出了针对上述模型的改进遗传算法.最后,以上海市交通道路生鲜农产品配送作为案例,对算法进行测试.
In this paper, a vehicle routing optimization model with soft time windows is established for multi-varieties fresh agricultural products. The model takes the total cost of distribution as the minimum, which takes freshness threshold of fresh agricultural products and time window as constraints. Then, an improved genetic algorithm for the model is proposed by adding the Dijkstra algorithm and improving the crossover operator. Finally, the algorithm is tested through the distribution of fresh agricultural products in Shanghai.
In this paper, a vehicle routing optimization model with soft time windows is established for multi-varieties fresh agricultural products. The model takes the total cost of distribution as the minimum, which takes freshness threshold of fresh agricultural products and time window as constraints. Then, an improved genetic algorithm for the model is proposed by adding the Dijkstra algorithm and improving the crossover operator. Finally, the algorithm is tested through the distribution of fresh agricultural products in Shanghai.
引文
[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91.
[2]潘雯雯,郭海湘等.基于两阶段算法的需求可拆分多车型车辆路径问题[J].中国管理科学,2016(S1):55-61.
[3]颜瑞,朱晓宁等.考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J].中国管理科学,2017, 25(7):67-77.
[4]肖建华,王超文等.基于城市道路限行的多能源多车型车辆路径优化[J].系统工程理论与实践,2017,37(5):1339-1348.
[5] Thibaut V, Teodor Gabriel Crainic, 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(1):475-489.
[6] Esam T Y, Masri Ayob, et al. Meta-harmony search algorithm for the vehicle routing problem with time windows[J]. Information Sciences, 2015, 325:140-158.
[7] Simen B, Ola Gjonnes, et al. Heuristics for the robust vehicle routing problem with time windows[J].Expert Systems with Applications, 2017, 77:136-147.
[8] Mohammad S F, Haldun Sural, et al. A column generation approach for the location-routing problem with time windows[J]. Computers&Operations Research, 2018, 90:249-263.
[9]符卓,刘文等.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索箅法[J].中国管理科学,2017,25(5):78-86.
[10]杨鹏,邹浩等.带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J].系统工程,2015, 33(9):58-62.
[11] Jiuping X, Fang Yan, et al. Vehicle routing optimization with soft time windows in a fuzzy random environment[J]. Transportation Research Part E:Logistics and Transportation Review, 2011, 47(6):1075-1091.
[12] Sumaiya I, M. Kaykobad, et al. Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees[J]. Swarm and Evolutionary Computation, 2015, 24:50-64.
[13] Esmat Zare-Reisabadi, Hamid Mirmohammadi S. Site dependent vehicle routing problem with soft time window:Modeling and solution approach[J]. Computers&Industrial Engineering, 2015, 90:177-185.
[14] Ali K B, Seyed Reza Hejazi. A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences, 2015, 316:598-615.
[15]侯玉梅,贾震环等.带软时间窗整车物流配送路径优化研究[J].系统工程学报,2015, 30(2):240-250.
[16] Duygu T, Nico D, et al. Vehicle routing problem with stochastic travel times including soft time windows and service cost[J]. Computers&Operations Research, 2013, 40(1):214-224.
[17] Wan C C, Chen Yang Cheng. Considering the Performance Bonus Balance in the Vehicle Routing Problem with Soft Time Windows[J]. Procedia Manufacturing, 2017, 11:2156-2163.
[18] Jianquan G, Xinyue Wang, et al. Forward and reverse logistics network and route planning under the environment of low-carbon emissions:A case study of Shanghai fresh food E-commerce enterprises[J]. Computers&Industrial Engineering, 2017, 106:351-360.
[19] Aiying R, Renzo Akkerman, et al. An optimization approach for managing fresh food quality throughout the supply chain[J]. International Journal of Production Economics, 2011, 131(1):421-429.
[20] Ghaffari-Nasab N, Ghazanfar Ahari S, et al. A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J]. Scientia Iranica, 2013, 20(3):919-930.
[21] Slim B, Pierre H, et al. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers and Operations Reserch, 2014, 52:269-281.
[22] Kuo R J, Wibowo B S, et al. Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time[J]. Applied Mathematical Modelling, 2016, 40(23-24):9990-10001.
[23] Kevin D, Remy Spliet. A branch-and-cut algorithm for the time window assignment vehicle routing problem[J]. Computers&Operations Research, 2018, 89:140-152.
[24] Marwa H, Saoussen Krichen. Variable neighborhood descent for solving the vehicle routing problem with time windows[J]. Electronic Notes in Discrete Mathematics, 2017, 58:175-182.
[25] Erbao C, Ruotian Gao, et al. Research on the vehicle routing problem with interval demands[J].Applied Mathematical Modelling, 2018, 54:332-346.
[26]符卓,刘文等.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索箅法[J].中国管理科学,2017,25(5):78-86.
[27]熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015(5):1230-1235.
[28]李进,张江华.基于碳排放与速度优化的带时间窗车辆路径问题[J].系统工程理论与实践,2014, 34(12):3063-3072.
[29]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004, 18(1):81-84.
[2]潘雯雯,郭海湘等.基于两阶段算法的需求可拆分多车型车辆路径问题[J].中国管理科学,2016(S1):55-61.
[3]颜瑞,朱晓宁等.考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J].中国管理科学,2017, 25(7):67-77.
[4]肖建华,王超文等.基于城市道路限行的多能源多车型车辆路径优化[J].系统工程理论与实践,2017,37(5):1339-1348.
[5] Thibaut V, Teodor Gabriel Crainic, 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(1):475-489.
[6] Esam T Y, Masri Ayob, et al. Meta-harmony search algorithm for the vehicle routing problem with time windows[J]. Information Sciences, 2015, 325:140-158.
[7] Simen B, Ola Gjonnes, et al. Heuristics for the robust vehicle routing problem with time windows[J].Expert Systems with Applications, 2017, 77:136-147.
[8] Mohammad S F, Haldun Sural, et al. A column generation approach for the location-routing problem with time windows[J]. Computers&Operations Research, 2018, 90:249-263.
[9]符卓,刘文等.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索箅法[J].中国管理科学,2017,25(5):78-86.
[10]杨鹏,邹浩等.带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J].系统工程,2015, 33(9):58-62.
[11] Jiuping X, Fang Yan, et al. Vehicle routing optimization with soft time windows in a fuzzy random environment[J]. Transportation Research Part E:Logistics and Transportation Review, 2011, 47(6):1075-1091.
[12] Sumaiya I, M. Kaykobad, et al. Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees[J]. Swarm and Evolutionary Computation, 2015, 24:50-64.
[13] Esmat Zare-Reisabadi, Hamid Mirmohammadi S. Site dependent vehicle routing problem with soft time window:Modeling and solution approach[J]. Computers&Industrial Engineering, 2015, 90:177-185.
[14] Ali K B, Seyed Reza Hejazi. A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences, 2015, 316:598-615.
[15]侯玉梅,贾震环等.带软时间窗整车物流配送路径优化研究[J].系统工程学报,2015, 30(2):240-250.
[16] Duygu T, Nico D, et al. Vehicle routing problem with stochastic travel times including soft time windows and service cost[J]. Computers&Operations Research, 2013, 40(1):214-224.
[17] Wan C C, Chen Yang Cheng. Considering the Performance Bonus Balance in the Vehicle Routing Problem with Soft Time Windows[J]. Procedia Manufacturing, 2017, 11:2156-2163.
[18] Jianquan G, Xinyue Wang, et al. Forward and reverse logistics network and route planning under the environment of low-carbon emissions:A case study of Shanghai fresh food E-commerce enterprises[J]. Computers&Industrial Engineering, 2017, 106:351-360.
[19] Aiying R, Renzo Akkerman, et al. An optimization approach for managing fresh food quality throughout the supply chain[J]. International Journal of Production Economics, 2011, 131(1):421-429.
[20] Ghaffari-Nasab N, Ghazanfar Ahari S, et al. A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J]. Scientia Iranica, 2013, 20(3):919-930.
[21] Slim B, Pierre H, et al. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers and Operations Reserch, 2014, 52:269-281.
[22] Kuo R J, Wibowo B S, et al. Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time[J]. Applied Mathematical Modelling, 2016, 40(23-24):9990-10001.
[23] Kevin D, Remy Spliet. A branch-and-cut algorithm for the time window assignment vehicle routing problem[J]. Computers&Operations Research, 2018, 89:140-152.
[24] Marwa H, Saoussen Krichen. Variable neighborhood descent for solving the vehicle routing problem with time windows[J]. Electronic Notes in Discrete Mathematics, 2017, 58:175-182.
[25] Erbao C, Ruotian Gao, et al. Research on the vehicle routing problem with interval demands[J].Applied Mathematical Modelling, 2018, 54:332-346.
[26]符卓,刘文等.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索箅法[J].中国管理科学,2017,25(5):78-86.
[27]熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015(5):1230-1235.
[28]李进,张江华.基于碳排放与速度优化的带时间窗车辆路径问题[J].系统工程理论与实践,2014, 34(12):3063-3072.
[29]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004, 18(1):81-84.