Titel:Probabilistic analysis of euclidean multi depot vehicle routing and related problems

Autor:Sören Werth

URN:NBN:urn:nbn:de:gbv:8-diss-19927

Fakultät:Technische Fakultät
DDC Sachgebiet:004 Informatik

Datum der mdl. Prüfung:20.12.2006

Referent(in):Prof. Dr. Anand Srivastav
Korreferent(en) Korreferentin:Prof. Dr. Klaus Jansen

Beschreibung:We consider a generalization of the classical traveling salesman problem: the multi depot vehicle routing problem (MDVRP). Let $D$ be a set of $k$ depots and $P$ be sets $n$ customers in $[0,1]^d$ with the usual Euclidean metric. A multi depot vehicle routing tour is a set of disjoint cycles such that all customers are covered and each cycle contains exactly one depot. The goal is to find a tour of minimum length. $L(D,P)$ denotes the length of an optimal MDVRP tour for depot set $D$ and customer set $P$. It is evident that the asymptotic behavior of $\L(D,P)$ for $n$ tending to infinity depends on the customer-depot ratio $n/k$. We study three cases: $k=o(n)$, $k=\lambda n +o(n)$ for a constant $\lambda >0$, and $k=\Omega(n^{1+\ee})$ for $\ee>0$. In the first two cases we show that $L(D,P)$ divided by $n^{(d-1)/d}$ converges completely to a constant if the customers and depots are given by iid random variables. In the last case we prove that the expected tour length divided by $n^{(d-1)/d}$ and multiplied by $k^{1/d}$ converges to a constant if the customers and depots are given by iid random variables with uniform distribution.

Schlagworte:Probabilistic Analysis, Euclidean MDVRP, degree constrained MST

Dokumente: