Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A vector evaluated evolutionary algorithm with exploitation reinforcement for the dynamic pollution routing problem

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper, we investigate the Pollution Routing Problem in dynamic environments (DPRP). It consists in determining the routing plan of a fleet of vehicles supplying a set of customers, while minimizing the traveled distance and \(CO_2\) emissions. The dynamic character of the problem is manifested by the occurrence of new customer demands when the working plan is in progress. Consequently, the planned routes have to be adapted in real time to include the locations of the new customers. In order to efficiently manage the trade-off between the two considered objectives, a new vector evaluated evolutionary algorithm augmented with an exploitation phase and hyper-mutation is proposed. This combination aims to reinforce the refinement of compromised solutions, and to speed up adaptation after the occurrence of a change in the problem inputs. An experimental study is conducted to test the proposed approaches on mono-objective and bi-objective test problems, and against well known approaches from the literature. The obtained results show that our proposal performs well and is highly competitive compared with the competing meta-heuristics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data Availability

Enquiries about data availability should be directed to the authors.

Materials Availability

All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.

The authors have no financial or proprietary interests in any material discussed in this article.

References

  • Abdallah AMF, Essam DL, Sarker RA (2017) On solving periodic re-optimization dynamic vehicle routing problems. Appl Soft Comput 55:1

    Google Scholar 

  • Alizadeh Foroutan R, Rezaeian J, Mahdavi I (2020) Green vehicle routing and scheduling problem with heterogeneous fleet including reverse logistics in the form of collecting returned goods. Appl Soft Comput 94:106462

    Google Scholar 

  • Arjmand M, Najafi AA (2015) Solving a multi-mode bi-objective resource investment problem using meta-heuristic algorithms. Advanced Computational Techniques Electromagnetics 1:41

    Google Scholar 

  • Asefi H, Jolai F, Rabiee M, Tayebi Araghi ME (2014) A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem. The International Journal Advanced Manufacturing Technology 75(5):1017

    Google Scholar 

  • Asghari M, Al-e SMJM et al (2020) A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources. Transportation Research Part E: Logistics Transportation Review 134:101815

    Google Scholar 

  • Asghari M, Al-e SMJM et al (2021) Green vehicle routing problem: A state-of-the-art review. Int J Prod Econ 231:107899

    Google Scholar 

  • Azzouz R, Bechikh S, Ben Said L (2017) Dynamic Multi-objective Optimization Using Evolutionary Algorithms: A Survey. Springer International Publishing, Cham, pp 31–70

    Google Scholar 

  • Bektaş T, Laporte G (2011) The pollution-routing problem. Transportation Research Part B: Methodological 45(8):1232

    Google Scholar 

  • Ben-Romdhane H, Alba E, Krichen S (2013) Best practices in measuring algorithm performance for dynamic optimization problems. Soft Comput 17(6):1005

    Google Scholar 

  • Chen S, Chen R, Wang GG, Gao J, Sangaiah AK (2018) An adaptive large neighborhood search heuristic for dynamic vehicle routing problems. Comput Electr Eng 67:596–607

    Google Scholar 

  • Dabia S, Demir E, Woensel TV (2017) An exact approach for a variant of the pollution-routing problem. Transp Sci 51(2):607

    Google Scholar 

  • de Armas J, Melián-Batista B (2015) Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with time windows. Computers & Industrial Engineering 85:120

    Google Scholar 

  • Dekker R, Bloemhof J, Mallidis I (2012) Operations Research for green logistics - An overview of aspects, issues, contributions and challenges. Eur J Oper Res 219(3):671

    Google Scholar 

  • Demir E, Bektaş T, Laporte G (2014) The bi-objective pollution-routing problem. Eur J Oper Res 232(3):464

    MathSciNet  MATH  Google Scholar 

  • Djavadian S, Tu R, Farooq B, Hatzopoulou M (2020) Multi-objective eco-routing for dynamic control of connected & automated vehicles. Transp Res Part D: Transp Environ 87:102513

    Google Scholar 

  • Ehmke JF, Campbell AM, Thomas BW (2016) Vehicle routing to minimize time-dependent emissions in urban areas. Eur J Oper Res 251(2):478

    MathSciNet  MATH  Google Scholar 

  • El Bouzekri E, El Idrissi Adiba, Ahemd HA (2014) Evolutionary algorithm for the bi-objective green vehicle routing problem. International Journal of Scientific & Engineering Research 5(9):70

  • Erdoĝan S, Miller-Hooks E (2012) A Green Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review 48(1):100 . Select Papers from the 19th International Symposium on Transportation and Traffic Theory

  • Eshtehadi R, Fathian M, Demir E (2017) Robust solutions to the pollution-routing problem with demand and travel time uncertainty. Transp Res Part D: Transp Environ 51:351

    Google Scholar 

  • Eskandarpour M, Ouelhadj D, Hatami S, Juan AA, Khosravi B (2019) Enhanced multi-directional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges. Eur J Oper Res 277(2):479

    MathSciNet  MATH  Google Scholar 

  • Fan H, Zhang Y, Tian P, Lv Y, Fan H (2021) Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance. Computers & Operations Research 129:105211

    MathSciNet  MATH  Google Scholar 

  • Franceschetti A, Honhon D, Van Woensel T, Bektaş T, Laporte G (2013) The time-dependent pollution-routing problem. Transportation Research Part B: Methodological 56:265

    Google Scholar 

  • Franceschetti A, Demir E, Honhon D, Van Woensel T, Laporte G, Stobbe M (2017) A metaheuristic for the time-dependent pollution-routing problem. Eur J Oper Res 259(3):972

    MathSciNet  MATH  Google Scholar 

  • García-Martínez C, Rodriguez FJ, Lozano M (2018) Genetic Algorithms. Springer International Publishing, Berlin, pp 431–464

    Google Scholar 

  • Goh CK, Tan KC (2009) A Competitive-cooperative Coevolutionary Paradigm for Dynamic Multiobjective Optimization. Trans. Evol. Comp 13(1):103

    Google Scholar 

  • Habibi F, Barzinpour F, Sadjadi SJ (2017) A Multi-objective optimization model for project scheduling with time-varying resource requirements and capacities. Journal Industrial Systems Engineering 10:92

    Google Scholar 

  • Hong L (2012) An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers & Operations Research 39(2):151

    MATH  Google Scholar 

  • Ishibuchi H, Masuda H, Nojima Y (2014) Selecting a small number of non-dominated solutions to be presented to the decision maker. In: 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (IEEE), pp 3816–3821

  • Jabali O, Van Woensel T, De Kok A (2012) Analysis of travel times and CO2 emissions in time-dependent vehicle routing. Prod Oper Manag 21(6):1060

    Google Scholar 

  • Jaw JJ, Odoni AR, Psaraftis HN, Wilson NH (1986) A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological 20(3):243

    Google Scholar 

  • Jun Q, Wang J, Zheng Bj (2008) A Hybrid Multi-objective Algorithm for Dynamic Vehicle Routing Problems. In: Bubak M, van Albada GD, Dongarra J, Sloot PMA (eds) Computational Science - ICCS 2008. Springer, Berlin Heidelberg, pp 674–681

    Google Scholar 

  • Koç Ç, Bektaş T, Jabali O, Laporte G (2014) The fleet size and mix pollution-routing problem. Transportation Research Part B: Methodological 70:239

    MATH  Google Scholar 

  • Kontovas CA, Psaraftis HN (2016) Transportation emissions: Some basics. In: Green transportation logistics (Springer), pp. 41–79

  • Kramer R, Subramanian A, Vidal T, dos Anjos L, Cabral F (2015) A matheuristic approach for the Pollution-Routing Problem. Eur J Oper Res 243(2):523

    MathSciNet  MATH  Google Scholar 

  • Larsen A, Madsen OB, Solomon MM (2008) Recent developments in dynamic vehicle routing systems. The Vehicle Routing Problem: Latest Advances New Challenges 43:199

    MathSciNet  MATH  Google Scholar 

  • Lin C, Choy K, Ho G, Chung S, Lam H (2014) Survey of Green Vehicle Routing Problem: Past and future trends. Expert Syst Appl 41(4, Part 1):1118

    Google Scholar 

  • Liu X, Luo J (2019) A dynamic multi-objective optimization model with interactivity and uncertainty for real-time reservoir flood control operation. Appl Math Model 74:606

    MathSciNet  MATH  Google Scholar 

  • Liu M, He J (2009) A hybrid genetic algorithm with hyper-mutation and elitist strategies for automated analog circuit design. In: 2009 International Workshop on Intelligent Systems and Applications (IEEE), pp. 1–4

  • Lund K, Madsen OB, Rygaard JM (1996) Vehicle routing problems with varying degrees of dynamism (IMM Institute of Mathematical Modelling)

  • Moghdani R, Salimifard K, Demir E, Benyettou A (2020) The green vehicle routing problem: A systematic literature review. J Clean Prod 279:123691

    Google Scholar 

  • Molina JC, Eguia I, Racero J, Guerrero F (2014) Multi-objective vehicle routing problem with cost and emission functions. Procedia Soc Behav Sci 160:254

    Google Scholar 

  • Naderipour M, Alinaghian M (2016) Measurement, evaluation and minimization of CO2, NOx, and CO emissions in the open time dependent vehicle routing problem. Measurement 90:443

    Google Scholar 

  • Nguyen TT, Yang S, Branke J (2012) Evolutionary dynamic optimization: A survey of the state of the art. Swarm Evol Comput 6:1

    Google Scholar 

  • Okulewicz M, Mańdziuk J (2017) The impact of particular components of the PSO-based algorithm solving the Dynamic Vehicle Routing Problem. Appl Soft Comput 58:586

    Google Scholar 

  • Olgun B, Koç Çağrı, Altıparmak F (2021) A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering 153:107010

    Google Scholar 

  • Ombuki B, Ross BJ, Hanshar F (2006) Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl Intell 24(1):17

    Google Scholar 

  • Ouertani N, Ben-Romdhane H, Krichen S (2020) A decision support system for the dynamic hazardous materials vehicle routing problem. Oper Res Int J. https://doi.org/10.1007/s12351-020-00562-w

    Article  Google Scholar 

  • Ouertani N, Ben-Ramdhan H, Krichen S, Nouaouri I, Allaoui H (2018) A New Evolutionary Method to Deal with the Dynamic Vehicle Routing Problem. In: 2018 IEEE International Conference on Technology Management, Operations and Decisions (ICTMOD) (IEEE), pp 1–5

  • Ouertani N, Nouaouri I, Ben-Romdhane H, Allaoui H, Krichen S (2019) A Hypermutation Genetic Algorithm for the Dynamic Home Health-Care Routing Problem. In: 2019 International Conference on Industrial Engineering and Systems Management (IESM), pp 1–6

  • Pillac V, Gendreau M, Guńret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Oper Res 225(1):1

    MathSciNet  MATH  Google Scholar 

  • Psaraftis HN (1995) Dynamic vehicle routing: Status and prospects. Ann Oper Res 61(1):143

    MATH  Google Scholar 

  • Psaraftis HN (2016) Green Transportation Logistics. Springer, Berlin

    Google Scholar 

  • Qiu R, Xu J, Ke R, Zeng Z, Wang Y (2020) Carbon pricing initiatives-based bi-level pollution routing problem. Eur J Oper Res 286(1):203

    MathSciNet  MATH  Google Scholar 

  • Raeesi R, Zografos KG (2019) The multi-objective Steiner pollution-routing problem on congested urban road networks. Transportation Research Part B: Methodological 122:457

    Google Scholar 

  • Rauniyar A, Nath R, Muhuri PK (2019) Multi-factorial evolutionary algorithm based novel solution approach for multi-objective pollution-routing problem. Computers & Industrial Engineering 130:757

    Google Scholar 

  • Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54(1):215

    MATH  Google Scholar 

  • Sabar NR, Bhaskar A, Chung E, Turky A, Song A (2019) A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm Evol Comput 44:1018

    Google Scholar 

  • Sadati MEH, Çatay B (2021) A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem. Transportation Research Part E: Logistics Transportation Review 149:102293

    Google Scholar 

  • Sbihi A, Eglese RW (2007) The Relationship between Vehicle Routing & Scheduling and Green Logistics - A Literature Survey . Department of Management Science, Lancaster University Management School, LA1 4YX, UK

  • Schaffer JD (1985) Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. In: Proceedings of the 1st International Conference on Genetic Algorithms (L. Erlbaum Associates Inc., Hillsdale, NJ, USA), pp 93–100

  • Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, vol. 35(2): (mar.-apr., 1987) 35, 254

  • Talbi EG (2009) Metaheuristics: From Design to Implementation (Wiley Publishing)

  • Xiao Y, Konak A (2017) A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem. J Clean Prod 167:1450

    Google Scholar 

  • Xiao Yiyong, Zuo Xiaorong, Huang Jiaoying, Konak Abdullah, Xu Yuchun (2020) The continuous pollution routing problem. Appl Math Comput 387:125072

    MATH  Google Scholar 

  • Yang Z, van Osta JP, van Veen B, van Krevelen R, van Klaveren R, Stam A, Kok J, Bäck T, Emmerich M (2017) Dynamic vehicle routing with time windows in theory and practice. Nat Comput 16(1):119

    MathSciNet  MATH  Google Scholar 

Download references

Funding

The authors have not disclosed any funding.

Author information

Authors and Affiliations

  1. LARODEC Laboratory, Université de Tunis, Institut Supérieur de Gestion de Tunis, Tunis, Tunisia

    Nasreddine Ouertani, Hajer Ben-Romdhane & Saoussen Krichen

  2. LGI2A Laboratory, Université d’Artois, UR 3926 LGI2A 62400, Béthune, France

    Nasreddine Ouertani & Issam Nouaouri

Authors
  1. Nasreddine Ouertani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hajer Ben-Romdhane
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Saoussen Krichen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Issam Nouaouri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nasreddine Ouertani.

Ethics declarations

Conflict of interests

The authors have no conflicts of interest to declare that are relevant to the content of this article.

Discloser

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

A Diversification matrix

The diversification matrix DM measures the diversity of solutions based on their spread in the POF. A higher value of DM implies that the algorithm has a better capability in terms of diversification. The DM performance measure is presented in Eq. (17) (Asefi et al. 2014):

$$\begin{aligned} DM = \sqrt{ (maxf_{1i} - minf_{1i})^{2} + (maxf_{2i} - minf_{2i})^{2}} \end{aligned}$$
(17)

In this equation, maxf1i and minf1i indicate respectively the maximum and the minimum values of \(i^{th}\) objective function achieved by non-dominated solution.

B Mean Ideal distance measure

The mean ideal distance measure MID calculates the closeness between the POF and the ideal point. As we deal with a minimization problem, the ideal point has the coordinate (0, 0). In view of this definition, the most efficient algorithm is the one with the lowest MID value. MID is given by, Habibi et al. (2017):

$$\begin{aligned} MID = \frac{\sum _{i=1}^{n} C_i }{n} \end{aligned}$$
(18)

where n is the number of non-dominated solutions and \(C_i\) is defined as: \(C_i = \sqrt{f_{1i}^{2}+f_{2i}^{2}}\) with \(f_{1i}\) and \(f_{2i}\) being -respectively- the first and the second objective values of the \(i^{th}\) non-dominated solution.

C Pareto dominance indicator

The Pareto Dominance Indicator PDI compares the ratio of non-dominated solutions provided by a particular solution set to the non-dominated solutions provided by all algorithms. The PDI metric is formulated in Eq. (19) and as it is clear that higher values are preferred to lower ones (Goh and Tan 2009).

$$\begin{aligned} PDI(X_{1},X_{2},...,X_{m}) = \frac{\left| X_{i} \bigcap Y \right| }{\left| Y \right| } \end{aligned}$$
(19)

where, \(Y = \left\{ y_{i} \right| \forall y_{i}, \lnot \exists x_{j} \in (X_{1} \cup X_{2} \cup ...\cup X_{m})< y_{i}\}\), and \(x_{j} < y_{i}\) implies that \(x_{j}\) dominates \(y_{i}\). \(X_{i}\) is the set of solution under evaluation.

D Non-dominated solutions

The NDS performance measure is calculated by counting the number of solutions in the POF obtained by each algorithm. The larger is the value of NDS, the better is the performance of the algorithm (Arjmand and Najafi 2015).

E Normalized score

The Normalized Score (NS) metric is used to compare algorithm’s efficiency through different problem instances and/or many change periods (for dynamic problem) (Nguyen et al. 2012). The NS calculates the performance of the \(i^{th}\) algorithm by normalizing the results given by each algorithm to the range (0, 1). Using this metric, the best performing algorithm will get the highest overall score. The NS formula of the \(i^{th}\) algorithm is given by:

$$\begin{aligned} NS(A,i) = \frac{1}{N} \sum _{i=1}^{N} \frac{\mid (Alg(A,i) - MIN(i))\mid }{\mid (MAX(i) - MIN(i))\mid } \end{aligned}$$
(20)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ouertani, N., Ben-Romdhane, H., Krichen, S. et al. A vector evaluated evolutionary algorithm with exploitation reinforcement for the dynamic pollution routing problem. J Comb Optim 44, 1011–1038 (2022). https://doi.org/10.1007/s10878-022-00870-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-022-00870-1

Keywords

Search

Navigation