Capacitated Vehicle Routing Problem - Algorithm and Relaxation

Hi,

I´m trying to write some code in order to find a good approximation to
the solution of a Capacitated Vehicle Routing Problem (similar to the
Multiple Traveling Salesman Problem). I am aware that´s an NP-hard
problem.

The objective of the CVRP is to deliver a set of customers with known
demands on minimum-cost vehicle routes originating and terminating at a
depot, considering there are K vehicles and each of them has a limited
capacity Q. All the routes must start and end at the depot.

The depot and the customers (or cities) are represented by vertices and
the roads between them are represented by edges. Each vertice has a
demand. Each edge has a weight, corresponding to the distance between
the cities. The depot has a fictional demand of 0.

Essentially it comes down to finding out the K routes (one for each
vehicle) such that each route does not exceed capacity Q and the total
cost (distance) is minimum.

I want to use a branch-and-bound strategy, branching on arcs. With this
type of branching, an arc (xi, xj) is chosen for branching at a node of
the search tree in order to extend a partially completed route (xo, xk,
.... ,xi). The alternative branching is to reject arc (xi, xj) as a
possible extension of the route. I am also aware I need some relaxation
method in order to reach a feasible solution in polynomial time.

Does anybody have an idea of what relaxation could be used in this
case? I wish to keep the program as simple as possible. Additionaly,
what would be the best criteria to choose the next arc to be
included/excluded when branching? Does anybody have an idea (draft) of
how to implement this algorithm?

I´d appreciate any help or pointers.

--Markus

.

Relevant Pages

  • Re: Broad standards acceptance
    ... There was supposed to be some "heritage" routes but ISTR ... outclassed by even the most basic modern vehicle. ... And except for the fact that the Routemasters still in service on ... you can hop on and off while the bus is held up in traffic. ...
    (comp.sys.acorn.misc)
  • Re: Seen elswhere... ban JCBs...
    ... And banning JCBs (unless crrying out ... > motorways - in fct, they are part of the same network as the ... but even those older routes had been built as bypasses ... designated as special roads upon which only specific classes of vehicle are ...
    (uk.rec.driving)
  • Re: Passing stationary / parked cars
    ... show that there was a genuine necessity for their vehicle to be parked ... I thought a garage was somewhere to store a vehicle - apparently the word comes from a French word to 'shelter'. ... There are other routes available but as our road was once a handy mud-track that joined up two small settlements and also led to the manor house it's a very useful road. ...
    (uk.rec.cycling)
  • Re: Plan. Weekend. OUENDAAA....Ah, Gaming.
    ... and apart from a difficulty cliff to climb in the first race it's great fun. ... (It's all apart the vehicle you choose and the routes you pick. ...
    (uk.games.video.misc)