Exportar Publicação

Nunes, Ana Catarina, Mourão, Maria Cândida, L. Gouveia & Constantino, Miguel (2013). Contiguity service constraints for capacitated arc routing problems. WARP 1 - 1st Workshop on Arc Routing Problems.

A. C. Nunes et al.,  "Contiguity service constraints for capacitated arc routing problems", in WARP 1 - 1st Workshop on Arc Routing Problems, Copenhaga, 2013

@misc{nunes2013_1734884744612,
	author = "Nunes, Ana Catarina and Mourão, Maria Cândida and L. Gouveia and Constantino, Miguel",
	title = "Contiguity service constraints for capacitated arc routing problems",
	year = "2013",
	howpublished = "Outro",
	url = "http://econ.au.dk/arc-routing/"
}

TY  - CPAPER
TI  - Contiguity service constraints for capacitated arc routing problems
T2  - WARP 1 - 1st Workshop on Arc Routing Problems
AU  - Nunes, Ana Catarina
AU  - Mourão, Maria Cândida
AU  - L. Gouveia
AU  - Constantino, Miguel
PY  - 2013
CY  - Copenhaga
UR  - http://econ.au.dk/arc-routing/
AB  - Capacitated arc routing problems are used to manage the activities over the links (arcs and edges) of a graph performed by vehicles with limited capacity. The household refuse collection in urban areas may be modeled by such problems. In particular, we will focus on the mixed capacitated arc routing problem (MCARP) and on the sectoring-arc routing problem (SARP), both defined over a mixed multigraph, since this better holds street map characteristics  underlying in household refuse collection applications.
The MCARP consists of finding the trips starting and ending at the depot, serving all the required links and satisfying vehicles capacity, at minimum total duration. In the SARP, the subset of required links is partitioned into a fixed number of sectors and, for each sector, a set of MCARP trips, within a given time limit, is achieved.
In real world applications, such as the household refuse collection, it is also desirable to ensure the contiguity of the service for each vehicle, thus favoring the concentration of the service of each vehicle in a zone and avoiding vehicles’ intersection while servicing. However, this kind of practical requirement is not usually contemplated in linear programming formulations for capacitated arc routing problems when mixed graphs are considered.
Keeping this in mind, we will discuss linear constraints that may be added to force the contiguity of the links served by each vehicle (trip or sector), meaning that the subgraph induced by the links served by each vehicle is connected.
Computational results will be reported and analyzed over sets of benchmark problems.
ER  -