New upper bounds for the multi-depot capacitated arc routing problem

DOI10.1504/IJMHEUR.2010.033124MaRDI QIDQ537994zbMATH OpenOpenAlexFDO

Authors Ali Kansou, Adnan Yassine

Publication date 23 May 2011

Published in International Journal of Metaheuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijmheur.2010.033124

zbMATH Keywords

ant colony optimisationinsertion heuristicMD-CARPmemetic algorithmmulti-depot capacitated arc routing problem

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: The multi-depot capacitated arc routing problem (MD-CARP) generalises the well-known capacitated arc routing problem (CARP) by extending the single depot to a multi-depot network. The CARP consists of designing a set of vehicle trips, so that each vehicle starts and ends at the single depot. The MD-CARP involves the assignment of edges, which have to be served, to depots and the determination of vehicle trips for each depot. The first proposed work is based on ant colony optimisation (ACO) combined with an insertion heuristic: the ACO is used to optimise the order of insertion of the edges and the heuristic is devoted to inserting each edge in the solution. The second one is a memetic algorithm based on a special crossover. The computational results on benchmark instances show the satisfactory quality of the proposed methods and the superiority of the memetic algorithm compared to the ACO method.

Recommendations

• Lower and upper bounds for the mixed capacitated arc routing problem
• New lower bounds for the Capacitated Arc Routing Problem
• New lower bound for the capacitated arc routing problem
• Improved bounds for large scale capacitated arc routing problem
• Improved lower bounds and exact algorithm for the capacitated arc routing problem
• The Capacitated Arc Routing Problem: Lower bounds
• An approach to the asymmetric multi-depot capacitated arc routing problem
• Lower and upper bounds for location-arc routing problems with vehicle capacity constraints
• Lower bounds for the mixed capacitated arc routing problem
• The capacitated arc routing problem: Valid inequalities and facets

Cited in

(9)

• An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem
• Implicit depot assignments and rotations in vehicle routing heuristics
• On games arising from multi-depot Chinese postman problems
• New max min ant colony optimization for the periodic arc routing problem
• An approach to the asymmetric multi-depot capacitated arc routing problem
• An Evolutionary Algorithm with Distance Measure for the Split Delivery Capacitated Arc Routing Problem
• Crossover iterated local search for SDCARP
• A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem
• An improved multi-objective framework for the rich arc routing problem

This page was built for publication: New upper bounds for the multi-depot capacitated arc routing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537994)