Affordable Access

Publisher Website

Capacitated arc routing problem with deadheading demands

Authors
Journal
Computers & Operations Research
0305-0548
Publisher
Elsevier
Publication Date
Volume
39
Issue
10
Identifiers
DOI: 10.1016/j.cor.2011.12.008
Keywords
  • Capacitated Arc Routing Problem
  • Deadheading Edge Demands
  • Mathematical Model
  • Constructive Heuristic
  • Post-Optimization Procedure
Disciplines
  • Computer Science

Abstract

Abstract Capacitated arc routing problem (CARP) is the determination of vehicle tours that serve all positive-demand edges (required edge) exactly once without exceeding vehicle capacity while minimizing sum of all tour costs. In CARP, total demand of a tour is calculated by means of all required edges on the tour. In this study, a new CARP variation is introduced, which considers not only required edges but also traversed edges while calculating total demand of the tour. The traversing demand occurs when the traversed edge is either servicing or non-servicing (deadheading). Since the new CARP formulation incurs deadheading edge demands it is called CARP with deadheading demands. An integer linear model is given for the problem which is used to solve small-sized instances, optimally. A constructive heuristic is presented to solve the problem which is a modified version of a well-known CARP heuristic. Furthermore, two post-optimization procedures are presented to improve the solution of the heuristic algorithm. The effectiveness of the proposed methods is shown on test problems, which are obtained by modifying CARP test instances.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

The fleet size and mix problem for capacitated arc...

on European Journal of Operationa... Jan 01, 1985

The undirected capacitated arc routing problem wit...

on Computers & Operations Researc...

A cutting plane algorithm for the capacitated arc...

on Computers & Operations Researc... Jan 01, 2003

Approximate solutions for the capacitated arc rout...

on Computers & Operations Researc... Jan 01, 1989
More articles like this..