CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Probabilistic analysis for a multiple depot vehicle routing problem

A. Baltz ; Devdatt Dubhashi (Institutionen för data- och informationsteknik (Chalmers)) ; A. Srivastav ; Libertad Tansini (Institutionen för data- och informationsteknik (Chalmers)) ; S. Werth
Random structures & algorithms (1042-9832). Vol. 30 (2007), 1-2, p. 206-225.
[Artikel, refereegranskad vetenskaplig]

We give a probabilistic analysis of the Multiple Depot Vehicle Routing Problem (MDVRP) where k depots and it customers are given by i.i.d. random variables in [0, 1](d), d >= 2. The tour length divided by n((d-1)/d) tends to a integral([0,1]d) f(x)((d-1)/d) dx, where,f is the density of the absolutely continuous part of the law of the random variables giving the depots and customers and where the constant alpha depends on the number of depots. If k = o(n), alpha is the constant of the TSP problem. For k = lambda n, lambda > 0, we prove lower and upper bounds on alpha, which decrease as fast as (1 + lambda)(-1/d).

Nyckelord: probabilistic analysis, MDVRP, vehicle routing

Denna post skapades 2013-01-28.
CPL Pubid: 172293


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för data- och informationsteknik (Chalmers)


Teoretisk datalogi

Chalmers infrastruktur