Dissertation (Metadaten)
Titel:Probabilistic analysis of euclidean multi depot vehicle routing and related problems
Autor:Sören Werth
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
d1992.pdf (655 kB)    ZIP generieren   Details >>