An Optimization Model for Heterogeneous Vehicle Routing and Scheduling Problem with Fixed Cost and Green Reverse Logistics Network Using Genetic Algorithm

Document Type: Original Manuscript

Authors

1 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

2 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran.

10.22094/joie.2018.563565.1552

Abstract

Vehicle routing problem aims to find the optimal routes that must be traveled by a fleet of vehicles to satisfy the demand of the customers. In this research, the vehicle routing and scheduling problem is developed for a heterogeneous fleet with the fixed cost of applying vehicles and earliness and tardiness costs in a green reverse logistics network. Since the complexity order of these problems is higher than that of the polynomial ones, this problem is known as NP-hard. As the problem dimensions increase, the exact solving time of the problem increases considerably. Thus, metaheuristic methods are proposed to approximately solve these problems. After developing mixed integer nonlinear model, the Genetic Algorithm (GA) is used to find the near-optimal solutions for the large-scale cases. Finally, the performance of the GA is investigated for several examples by comparing its computation time and solution quality with the computation time and exact solution of the LINGO software. According to the results, the developed GA has an acceptable performance in providing solutions with minimum error in a rational time.

Graphical Abstract

An Optimization Model for Heterogeneous Vehicle Routing and Scheduling Problem with Fixed Cost and Green Reverse Logistics Network Using Genetic Algorithm

Highlights

  • A green vehicle routing and scheduling problem is considered in a reverse logistics network.
  • Earliness and tardiness costs, heterogeneous fleet and collecting returned goods are supposed.
  • The minimization of fuel consumption and also the emissions of CO2 are included.
  • A mixed integer non-linear programming model is developed.
  • An efficient genetic algorithm is proposed.

Keywords


Alshamsi, A. and Diabat, A. (2017) ‘A Genetic Algorithm for Reverse Logistics network design: A case study from the GCC’, Journal of Cleaner Production. Elsevier, 151, pp. 652–669.

Bektaş, T. and Laporte, G. (2011) ‘The pollution-routing problem’, Transportation Research Part B: Methodological, 45(8), pp. 1232–1250.

Bloemhof-Ruwaard, J. M. et al. (1995) ‘Interactions between operational research and environmental management’, European journal of operational research, 85(2), pp. 229–243.

De Bruecker, P. et al. (2018) ‘A model enhancement approach for optimizing the integrated shift scheduling and vehicle routing problem in waste collection’, European Journal of Operational Research. Elsevier, 266(1), pp. 278–290.

Chen, A., Yang, G. and Wu, Z. (2006) ‘Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem’, Journal of Zhejiang University-Science A. Springer, 7(4), pp. 607–614.

Clarke, G. and Wright, J. W. (1964) ‘Scheduling of vehicles from a central depot to a number of delivery points’, Operations research. Informs, 12(4), pp. 568–581.

Coelho, I. M. et al. (2016) ‘An integrated CPU–GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups’, International Journal of Production Research, 54(4), pp. 945–962.

Daniel, S. E., Diakoulaki, D. C. and Pappis, C. P. (1997) ‘Operations research and environmental planning’, European journal of operational research, 102(2), pp. 248–263.

Dantzig, G. B. and Ramser, J. H. (1959) ‘The truck dispatching problem’, Management science, 6(1), pp. 80–91.

Demir, E., Bektaş, T. and Laporte, G. (2012) ‘An adaptive large neighborhood search heuristic for the pollution-routing problem’, European Journal of Operational Research, 223(2), pp. 346–359.

Demir, E., Bektaş, T. and Laporte, G. (2014) ‘The bi-objective pollution-routing problem’, European Journal of Operational Research, 232(3), pp. 464–478.

Erdoğan, S. and Miller-Hooks, E. (2012) ‘A green vehicle routing problem’, Transportation Research Part E: Logistics and Transportation Review, 48(1), pp. 100–114.

Figliozzi, M. (2010) ‘Vehicle routing problem for emissions minimization’, Transportation Research Record: Journal of the Transportation Research Board, (2197), pp. 1–7.

Fisher, M. L. and Jaikumar, R. (1981) ‘A generalized assignment heuristic for vehicle routing’, Networks. Wiley Online Library, 11(2), pp. 109–124.

Franceschetti, A. et al. (2013) ‘The time-dependent pollution-routing problem’, Transportation Research Part B: Methodological, 56, pp. 265–293.

Gaur, D. R., Mudgal, A. and Singh, R. R. (2013) ‘Routing vehicles to minimize fuel consumption’, Operations Research Letters, 41(6), pp. 576–580.

Golden, B. L. and Wong, R. T. (1981) ‘Capacitated arc routing problems’, Networks. Wiley Online Library, 11(3), pp. 305–315.

Goli, A., Aazami, A. and Jabbarzadeh, A. (2018) ‘Accelerated Cuckoo Optimization Algorithm for Capacitated Vehicle Routing Problem in Competitive Conditions’, International Journal of Artificial IntelligenceTM, 16(1), pp. 88–112.

Holland, J. H. (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence.

Kara, I., Kara, B. and Yetis, M. K. (2007) ‘Energy minimizing vehicle routing problem’, Combinatorial optimization and applications, pp. 62–71.

Koç, Ç. et al. (2015) ‘A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows’, Computers & Operations Research, 64, pp. 11–27.

Kwon, Y.-J., Choi, Y.-J. and Lee, D.-H. (2013) ‘Heterogeneous fixed fleet vehicle routing considering carbon emission’, Transportation Research Part D: Transport and Environment, 23, pp. 81–89.

Laporte, G. (1992) ‘The vehicle routing problem: An overview of exact and approximate algorithms’, European journal of operational research. Elsevier, 59(3), pp. 345–358.

Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G. (1985) ‘The traveling salesman problem’. J. Wiley.

Lenstra, J. K. and Kan, A. H. G. (1981) ‘Complexity of vehicle routing and scheduling problems’, Networks, 11(2), pp. 221–227.

Lin, C. et al. (2014) ‘Survey of green vehicle routing problem: past and future trends’, Expert Systems with Applications, 41(4), pp. 1118–1138.

Lin, S.-W. et al. (2009) ‘Applying hybrid meta-heuristics for capacitated vehicle routing problem’, Expert Systems with Applications. Elsevier, 36(2), pp. 1505–1512.

Madankumar, S. and Rajendran, C. (2018) ‘Mathematical models for green vehicle routing problems with pickup and delivery: A case of semiconductor supply chain’, Computers & Operations Research. Elsevier, 89, pp. 183–192.

Malandraki, C. and Daskin, M. S. (1992) ‘Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms’, Transportation science, 26(3), pp. 185–200.

Mallidis, I. and Vlachos, D. (2010) ‘A Framework for green supply chain management’, in 1st Olympus international conference on supply chain, pp. 1–2.

Mirzapour Al-e-hashem, S. M. J. and Rekik, Y. (2014) ‘Multi-product multi-period Inventory Routing Problem with a transshipment option: A green approach’, International Journal of Production Economics, 157, pp. 80–88.

Niu, Y. et al. (2018) ‘Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost’, Journal of Cleaner Production. Elsevier, 171, pp. 962–971.

Renaud, J., Boctor, F. F. and Laporte, G. (1996) ‘An improved petal heuristic for the vehicle routeing problem’, Journal of the operational Research Society. Springer, 47(2), pp. 329–336.

Soleimani, H., Chaharlang, Y. and Ghaderi, H. (2018) ‘Collection and distribution of returned-remanufactured products in a vehicle routing problem with pickup and delivery considering sustainable and green criteria’, Journal of Cleaner Production. Elsevier, 172, pp. 960–970.

Soysal, M. (2016) ‘Closed-loop Inventory Routing Problem for returnable transport items’, Transportation Research Part D: Transport and Environment, 48, pp. 31–45.

Statistics, I. E. A. (2015) ‘CO2 emissions from fuel combustion-highlights’, IEA, Paris http://www. iea. org/co2highlights/co2highlights. pdf. Cited July.

Stern, H. I. and Dror, M. (1979) ‘Routing electric meter readers’, Computers & Operations Research. Elsevier, 6(4), pp. 209–223.

Tseng, Y., Yue, W. L. and Taylor, M. A. P. (2005) ‘The role of transportation in logistics chain’, in. Eastern Asia Society for Transportation Studies.

Varun Kumar, S. G. and Panneerselvam, R. (2017) ‘A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator’, Int. J. Comput. Intell. Res, 13(7), pp. 1717–1733.

Xiao, Y. and Konak, A. (2015) ‘A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness’, Applied Soft Computing, 34, pp. 372–388.

Xiao, Y. and Konak, A. (2017) ‘A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem’, Journal of Cleaner Production. Elsevier, 167, pp. 1450–1463.

Zhang, X. and Tang, L. (2009) ‘A new hybrid ant colony optimization algorithm for the vehicle routing problem’, Pattern Recognition Letters. Elsevier, 30(9), pp. 848–855.