Customer Traveling Salesman Problem (TSP)

at
Categories
Tags

 

You are the vehicle dispatcher for a delivery service that serves a mix of ‘easy’ customers who are quite pleasant when the driver arrives and ‘hard’ customers who are difficult to manage. In order to keep the drivers happy, you never assign a driver to visit two hard customers in a row. Thus, for each driver, given a set of ‘easy’ and ‘hard’ customers to visit, your goal is to minimize the travel time to visit all customers, starting and returning from the company depot, satisfying the constraint that a hard customer visit cannot be followed by another hard customer.

This problem can be infeasible if the number of hard customers is greater than the number of easy customers. Let’s assume that this is sometimes the case. As dispatcher, you have decided to relax the constraint that a hard customer visit cannot be followed by another hard customer. Rather, you want to minimize the number of times this happens and minimize the route travel length.

It may not be possible to minimize both terms at once; how would you find a good compromise?
Formulate the Hard/Easy Customer Traveling Salesman Problem (TSP) with the two term objective function terms. Define any new notation you introduce and explain your formulation in words and present mathematically.
Develop a heuristic to solve the problem. Clearly present your heuristic.

Sample Solution

Problem Formulation

The Hard/Easy Customer Traveling Salesman Problem (TSP) with the two term objective function can be formulated as follows:

Objective:

Minimize: f(x) = w1 * h(x) + w2 * d(x)

where:

  • w1 and w2 are non-negative weights that represent the relative importance of minimizing the number of hard customer visits and the route travel length, respectively.
  • h(x) is the number of times that a hard customer visit is followed by another hard customer visit in the route x.
  • d(x) is the total travel length of the route x.

Constraints:

(1) The route x must visit all customers, starting and returning from the company depot. (2) Each customer must be visited exactly once. (3) No hard customer visit can be followed by another hard customer visit, unless h(x) is minimized.

New Notation:

  • H is the set of hard customers.
  • E is the set of easy customers.
  • D is the distance matrix, where D[i][j] is the distance between customer i and customer j.
  • x is a route, which is a sequence of customers starting and returning from the company depot.

Formulation in Words

The objective of the problem is to minimize a weighted sum of two terms:

  • The number of times that a hard customer visit is followed by another hard customer visit in the route.
  • The total travel length of the route.

The constraints ensure that the route visits all customers, starting and returning from the company depot, and that each customer is visited exactly once. The third constraint ensures that no hard customer visit can be followed by another hard customer visit, unless the number of hard customer visits is minimized.

Mathematical Formulation

The problem can be mathematically formulated as follows:

Minimize: f(x) = w1 * h(x) + w2 * d(x)

subject to:

(1) For all customers i and j, if i is visited before j in the route x, then D[i][j] > 0.
(2) For all customers i, i is visited exactly once in the route x.
(3) For all customers i and j in H, if i is visited before j in the route x, then h(x) >= 1.
(4) The route x starts and returns from the company depot.

Heuristic

The following heuristic can be used to solve the Hard/Easy Customer Traveling Salesman Problem (TSP) with the two term objective function:

  1. Initialize the route x to a random permutation of all customers.
  2. Calculate the objective function value f(x) for the route x.
  3. While f(x) can be reduced:
    • If h(x) can be reduced without increasing d(x), then do so.
    • Otherwise, reduce d(x) using a local search algorithm, such as 2-opt or 3-opt.
  4. Return the route x.

This heuristic is greedy in the sense that it always makes the best local move, even if it does not lead to the global optimum. However, it has been shown to be effective in practice for a variety of TSP problems.

Example

Consider the following example of a Hard/Easy Customer Traveling Salesman Problem (TSP) with the two term objective function:

H = {1, 3, 5}
E = {2, 4, 6}
D = [[0, 10, 20, 30, 40, 50],
     [10, 0, 15, 25, 35, 45],
     [20, 15, 0, 10, 20, 30],
     [30, 25, 10, 0, 10, 20],
     [40, 35, 20, 10, 0, 10],
     [50, 45, 30, 20, 10, 0]]

The company depot is located at customer 0.

The following heuristic can be used to solve this problem:

  1. Initialize the route x to a random permutation of all customers, such as [0, 1, 2, 3, 4, 5, 6].
  2. Calculate

This question has been answered.

Get Answer