Cluster-First Route-Second Method

These methods perform a single clustering of the vertex set and then determine a vehicle route on each cluster. We will describe the next algorithms:

  • Fisher and Kaikumar
  • The Petal algorithm
  • The Sweep algorithm
  • Taillard

Fisher and Jaikumar Algorithm

The Fisher and Jaikumar algorithm [Fisher and Jaikumar 1981] is well known. It solves a Generalized Assignment Problem (GAP) to form the clusters. The number of vehicles ${K}$ is fixed. The algorithm can be described as follows:

  1. Seed Selection. Choose seed points ${j_{K}}$ in ${V}$ to initialize each cluster ${k}$.
  2. Allocation of Customers to Seeds. Compute the cost ${d_{ik}}$ of allocating each customer ${i}$ to each cluster ${k}$ as ${d_{ijk} = \min(c_{0i}+c_{ijk}+c_{j_{k}0},c_{0j_{k}}+c_{j_{k}i}+c_{i0})-c_{0j_{k}}+c_{j_{k}0}}$.
  3. Generalized Assignment. Solve a GAP with costs ${d_{ij}}$, customer weights ${q_{i}}$ and vehicle capacity ${Q}$.
  4. TSP Solution. Solve a TSP for each cluster corresponding to the GAP solution.

Petal Algorithm

A natural extension of the sweep algorithm is to generate several routes, called petals [Ryan, Hjorring and Glover 1993], and make a final selection by solving a set partitioning problem of the form:

$${\min \sum_{k\in S} d_{k}x{k}}$$

subject to:

$${\sum_{k\in S} a_{ik}x{k} = 1 (i = 1, \ldots, n)}$$

with

$${x_{k} = \left \lbrace 0, 1 \right \rbrace, k \in S}$$

where ${S}$ is the set of routes, ${x_{k} = 1}$ if and only if route ${k}$ belongs to the solution, ${a_{ik}}$ is the binary parameter equal to 1 only if vertex ${i}$ belongs to route ${k}$, and ${d_{k}}$ is the cost of petal ${k}$. If routes correspond to contiguous sectors of vertices, then this problem possesses the column circular property and be solved in polynomial time (Ryan, Hjorring and Glover).

The Sweep Algorithm

The sweep algorithm applies to planar instances of the VRP. It consists of two parts:

  • Split: Feasible clusters are initialed formed rotating a ray centered at the depot.
  • TSP: A vehicle routing is then obtained for each cluster by solving a TSP.

Some implementations include a post-optimization phase in which vertices are exchanged between adjacent clusters, and routes are reoptimized. A simple implementation of this method is as follows, where we assume that each vertex ${i}$ is represented by its polar coordinates ${(\theta_{i}, \rho_{i})}$, where ${\theta_{i}}$ is the angle and ${\rho_{i}}$ is the ray length. Assign a value ${\theta_{i}^{*} = 0}$ to an arbitrary vertex ${i^{*}}$ and compute the remaining angles from IMG6 ${(0,i^{*})}$. Rank the vertices in increasing order of their IMG2.

  1. Route Initialization. Choose an unused vehicle ${k}$.
  2. Route Construction. Starting from the unrouted vertex having the smallest angle, assign vertices to the vehicle ${k}$ as long as its capacity or the maximal route length is not exceeded. If unrouted vertices remain go to step 1.
  3. Route Optimization. Optimize each vehicle route separately by solving the corresponding TSP (exactly or approximately).

Taillard’s Algorithm

Talliard’s [Talliard 1993] algorithm defines neighborhood using the ${\lambda}$-interchange Generation mechanism [Osman 1993]. Individual routes are reoptimized using optimization algorithm of [Volgenant and Jonker 1993]. A nobel feature of Talliard’s algorithm is the decomposition of the main problems into subproblems.

In planar problems, these subproblems are obtained by initially partitioning vertices into sectors centered at the depot, and into concentric regions within each sector. Each subproblem can be solved independently, but periodical moves of vertices to adjacent sectors are necessary. This make sense when the depot is centered and vertices are uniformly distributed in the plane.

For non-planar problems, and for planar problems not possessing these properties, the author suggest a different partitioning method based on the computation of shortest spanning arborescences rooted at the depot. This decomposition method is particularly well suited for parallel implementation as subproblems can then be distributed among the various processors.

The combination of these strategies yields excellent computational results.