Sammendrag
In the literature, there has been a tendency to categorize applications as being either a case of node routing, or a case of arc routing. There are, however, important real-world problems whose essential characteristics cannot be captured neither by the CVRP nor by the CARP, as there is a mixture of requests located on nodes and requests located on links. Prins and Bouchenoua (2005) argue that in certain cases of urban-waste collection, most requests may be adequately modeled as located on streets, but some large point-based demands, located for example at schools or hospitals, are better modeled by the use of vertices. In subscription newspaper delivery, requests are basically located in points, but in dense urban or suburban residential areas a CARP model based on the street network may be a good abstraction. In general, qualified abstraction and problem reduction for a
CVRP instance through aggregation, for instance with heuristics based on the road network, will create an
instance with requests located on nodes, edges, and arcs. To answer the challenges that are induced by these complex problems, several researchers have recently focused their attention on the so-called Mixed Capacitated General Routing Problem (MCGRP). In the MCGRP, requests are located on a subset of vertices, edges, and arcs of a given weighted mixed graph, and a fleet of identical capacitated vehicles based at a central depot is used to satisfy requests with minimum routing cost while adhering to capacity constraints. The MCGRP is able to model a continuum of mixed node and arc routing problems, and hence removes the sharp boundary that is often seen in the literature. As alluded to above, the problem has large practical interest, particularly for so-called street routing applications. The MCGRP is also of interest in combinatorial optimization, because it generalizes both the CVRP, the CARP and many other routing problems. Its resulting combinatorial complexity is, however, very high, and solving it to optimality is a difficult task even for moderate-size instances. In this paper, we propose a novel, hybrid metaheuristic, called Adaptive Iterated Local Search (AILS) to solve large-size instances of the MCGRP. It utilizes vital mechanisms from two classical trajectory-based metaheuristics: Iterated Local Search (ILS), and Adaptive Large Neighborhood Search (ALNS). We have combined these mechanisms in a new way, and introduced several new elements. Novel local search and large neighborhood search operators have been designed, and well-known operators have been tailored to the problem at hand. When ALNS finds solutions with a certain quality, they are further intensified by local search (LS). We have designed a new, aggressive LS strategy. In each iteration we explore
the union of neighborhoods resulting from five operators, and try to execute all moves with positive savings.
In effect, we execute all independent moves before generating a new neighborhood. Our experimental study shows that the resulting algorithm is highly effective. For five MCGRP benchmarks consisting of 409 instances in total, AILS produces 402 best known solutions, 128 of which are new.
180 of the 402 solutions are proven optimal. One instance was closed for the first time by AILS. Notably, the AILS also achieves high quality computational results for heavily investigated special cases of the MCGRP, viz. four standard benchmarks for the CVRP, and seven standard benchmarks for the CARP.
CVRP instance through aggregation, for instance with heuristics based on the road network, will create an
instance with requests located on nodes, edges, and arcs. To answer the challenges that are induced by these complex problems, several researchers have recently focused their attention on the so-called Mixed Capacitated General Routing Problem (MCGRP). In the MCGRP, requests are located on a subset of vertices, edges, and arcs of a given weighted mixed graph, and a fleet of identical capacitated vehicles based at a central depot is used to satisfy requests with minimum routing cost while adhering to capacity constraints. The MCGRP is able to model a continuum of mixed node and arc routing problems, and hence removes the sharp boundary that is often seen in the literature. As alluded to above, the problem has large practical interest, particularly for so-called street routing applications. The MCGRP is also of interest in combinatorial optimization, because it generalizes both the CVRP, the CARP and many other routing problems. Its resulting combinatorial complexity is, however, very high, and solving it to optimality is a difficult task even for moderate-size instances. In this paper, we propose a novel, hybrid metaheuristic, called Adaptive Iterated Local Search (AILS) to solve large-size instances of the MCGRP. It utilizes vital mechanisms from two classical trajectory-based metaheuristics: Iterated Local Search (ILS), and Adaptive Large Neighborhood Search (ALNS). We have combined these mechanisms in a new way, and introduced several new elements. Novel local search and large neighborhood search operators have been designed, and well-known operators have been tailored to the problem at hand. When ALNS finds solutions with a certain quality, they are further intensified by local search (LS). We have designed a new, aggressive LS strategy. In each iteration we explore
the union of neighborhoods resulting from five operators, and try to execute all moves with positive savings.
In effect, we execute all independent moves before generating a new neighborhood. Our experimental study shows that the resulting algorithm is highly effective. For five MCGRP benchmarks consisting of 409 instances in total, AILS produces 402 best known solutions, 128 of which are new.
180 of the 402 solutions are proven optimal. One instance was closed for the first time by AILS. Notably, the AILS also achieves high quality computational results for heavily investigated special cases of the MCGRP, viz. four standard benchmarks for the CVRP, and seven standard benchmarks for the CARP.