0 Talk

1page on
this wiki

Home

Vehicle routing is a combinatorial optimization problem, where a service provider has to service a set of customers at different sites within specified time intervals. The goal is to maximize the number of customers serviced, while satisfying the timing constraints. This is a generalization of the traveling salesman problem.

There are two variations of this problem: Orienteering and Minimum Vehicle Routing.

Orienteering and related problems Edit

Input: Graph $G = (V, E)$ (undirected/directed); release times $R (v)$ and deadlines $D (v)$ , for all $v \in V$ ; start node $s$ and end node $t$ .

Objective: To collect as much reward as possible, while visiting vertex $v \in V$ within the interval $[R (v), D (v)]$ .

Output: A path $P$ from $s$ to $t$ with $\Pi_P \ge \alpha\Pi_{P^{\ast}}$ and $R(v) \le t_P(v) \le D(v)$ , for all $v \in P$ . Here, $α$ is the approximation factor and $Π P$ and $\Pi_{P^*}$ are the rewards collected by the output path $P$ and the optimum path $P *$ .

This is the most general version: Vehicle Routing with Time Windows, also known as Orienteering with Time Windows (ORIENT-TW).

If $R (v) = 0$ for all $v \in V$ , the problem is called Vehicle Routing with Deadlines, also known as Orienteering with Deadlines (ORIENT-DEADLINE) and Deadline-TSP.

If $D(v)=\infty$ for all $v \in V$ , the problem is called Vehicle Routing with Release Times, also known as Orienteering with Release Times (ORIENT-RELEASE). This problem is equivalent to ORIENT-DEADLINE.

If $R (v) = 0$ and $D (v) = D$ for all $v \in V$ , the problem is called Orienteering.

Minimum Vehicle Routing and related problems Edit

Papers Edit

Here is a summary of the results published in a few papers that we have read so far.

A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation Algorithms for Orienteering and Discounted-Reward TSP. SIAM J. on Computing, 37(2):653–670, 2007. Preliminary version in Proc. of IEEE FOCS, 46–55, 2003.

They gave the first constant-factor approximation algorithms for MIN-EXCESS-PATH (

2 + ε

), ORIENTEERING (4) and DISCOUNTED-REWARD-TSP ( $6.75+\varepsilon$ ) in undirected graphs, using an approximation algorithm for k-TSP. They also proved that ORIENTEERING is APX-hard to approximate within a factor of $\frac{1481}{1480}$ .

N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. Proc. of ACM STOC, 166–174, 2004.

They improved the approximation factor for ORIENTEERING to 3, and gave the first approximation algorithms for ORIENT-DEADLINE (

3log n

) and ORIENT-TW

(3log 2 n)

. They also gave a bi-criteria approximation algorithm for both problems: Given an

ε > 0

, their algorithm produces a $\log\left(\frac{1}{\epsilon}\right)$ approximation, while exceeding the deadlines by a factor of

1 + ε

C. Chekuri and M. Pal. A Recursive Greedy Algorithm for Walks in Directed Graphs. Proc. of IEEE FOCS, 245–253, 2005.

They gave a quasi-polynomial time

O (log O P T)

approximation algorithm for ORIENT-TW for both directed and undirected graphs, when the reward function is a given monotone submodular set function

f

V

, and the objective is to maximize

f (S)

where

S

is the set of vertices visited by the walk. They also gave an

O (log 2 k)

approximation for the k-TSP problem in directed graphs satisfying asymmetric triangle inequality, and an

O (log 2 k)

approximation for the group Steiner tree problem in undirected graphs, where

k

is the number of groups (both quasi-polynomial time).

V. Nagarajan and R. Ravi. Poly-logarithmic approximation algorithms for Directed Vehicle Routing Problems. Proc. of APPROX, 257–270, 2007.

They gave an

O (log 2 n log k)

approximation for k-TSP in directed graphs, using an

O (log 2 n)

approximation for the minimum ratio ATSP problem. They also proved that the integrality gap of a particular LP relaxation for ATSP is at most $\lceil \log n \rceil$ . Moreover, they gave a bi-criteria approximation for the directed k-PATH problem. Combining all these, they came up with an

O (log 2 n)

approximation for ORIENTEERING in directed graphs

C. Chekuri and N. Korula. Approximation Algorithms for Orienteering with Time Windows. Manuscript, September 2007.

They gave several algorithms for ORIENT-TW for the following scenarios:

An $O (αlog L max)$ approximation, when both $R (v)$ and $D (v)$ are integers for all $v \in V$ .
An $O (αmax{log O P T,log L})$ approximation.
An $O (αlog L)$ approximation when no start and end points are specified (unrooted version).

Here, $L(v) = D(v)-R(v), L_{\max} = \max_{v} L(v), L_{\min} = \min_{v} L(v), L = \frac{L_{\max}}{L_{\min}}$ and

α

is the approximation factor for ORIENTEERING.

C. Chekuri, N. Korula, and M. Pal. Improved Algorithms for Orienteering and Related Problems. Proc. of ACM-SIAM SODA, 661-670, 2008.

They improved the approximation factor for ORIENTEERING in undirected graphs to

2 + ε

, and gave an

O (log 2 O P T)

approximation algorithm for ORIENTEERING in directed graphs. They also gave an

O (log 3 k)

approximation for k-TSP in directed graphs.

Wikia

Vehicle Routing Algorithms

Home

Orienteering and related problems Edit

Minimum Vehicle Routing and related problems Edit

Papers Edit