How to model a TSP where the salesman can choose between flight, train and bus for every single connection?

Question

I want to model a multiobjective TSP where the salesman can choose between a flight, train and bus to go from city $i$ to city $j$. The aim of this multiobjective optimization problem is to minimize the cost (ticket prices), travel time and carbon emissions. (After getting the modeling right, I want to solve this problem with multiobjective evolutionary algorithms like NSGA-II and MOEA-D.)

This problem is applicable to tourists who are concerned about their carbon footprint while keeping their trip within budget and as comfortable as possible. For instance, a tourist doing a trip through Europe could choose whether to go by plane (short travel time, high carbon footprint) or by bus (the opposite) from city $i$ to city $j$.

So far, I have come up with the following model:

---

Variables

• $B_{ij}$, $F_{ij}$ and $T_{ij}$ are all binary, and equal $1$ if a bus/flight/train (respectively) is taken from city $i$ to city $j$ and $0$ otherwise.

Indices

• $N$ is the number of cities/locations to be visited;

• $i,j$ are the indices of cities that can take integer values from $1$ to $N$.

Parameters

• $p_{{B}_{ij}}$, $p_{{T}_{ij}}$, $p_{{F}_{ij}}$ are the prices in EUR for the bus/train/flight ticket respectively;

• $e_{{B}_{ij}}$, $e_{{T}_{ij}}$, $e_{{F}_{ij}}$ are the carbon dioxide levels emitted in kilograms by taking a bus/train/flight respectively to get from city $i$ to city $j$;

• $t_{{B}_{ij}}$, $t_{{T}_{ij}}$, $t_{{F}_{ij}}$ are the traveling times in minutes by taking a bus/train/flight respectively from city $i$ to city $j$.

---

Objective Functions

Minimize the cost $p$:

$$\min\sum_{i=1}^{N}\sum_{j=1}^{N}{\left(p_{B_{ij}}\cdot B_{ij}\right)+\left(p_{F_{ij}}\cdot T_{ij}\right)+\left(p_{T_{ij}}\cdot F_{ij}\right)}\tag1$$

Minimize carbon dioxide emissions $e$:

$$\min\sum_{i=1}^{N}\sum_{j=1}^{N}{\left(e_{B_{ij}}\cdot B_{ij}\right)+\left(e_{F_{ij}}\cdot T_{ij}\right)+\left(e_{T_{ij}}\cdot F_{ij}\right)}\tag2$$

Minimize the traveling time $t$:

$$\min\sum_{i=1}^{N}\sum_{j=1}^{N}{\left(t_{B_{ij}}\cdot B_{ij}\right)+\left(t_{F_{ij}}\cdot T_{ij}\right)+\left(t_{T_{ij}}\cdot F_{ij}\right)}\tag3$$

Constraints

\begin{align}\sum_{j=1\mid j\neq i}^NF_{ij}/T_{ij}/B_{ij}&=1,&\forall i=1,\ldots,N\tag4\\\sum_{i=1\mid i\neq j}^NF_{ij}/T_{ij}/B_{ij}&=1,&\forall j=1,\ldots,N\tag5\\\sum_{i,j\in S}F_{ij}/T_{ij}/B_{ij}&\le\left|S\right|-1,&\forall S\nsubseteq N\tag6\\F_{ij}/T_{ij}/B_{ij}&\in\left\{0,1\right\},&\forall i,j=1,\ldots,N\tag7\end{align}

---

Basically, I just adapted the classic TSP model and extended it by two more decision variables. But I am not sure if this would work, especially with the sub-tour elimination constraint (second last).

Answer 1

You can create three nodes for one city.

In other words, You create a bus station, train station, airport in one city. If you arrive in city A with a train but leave with a plane, you have to move from the train station to Airport. And then you can assign 0 (or appropriate quantities, emission or time) for moving between any of them within the same city.

There could be a better way to formulate because the number of nodes becomes 3 times in this way.

And Multi-objective part, You cannot solve the problem with three objectives, like LP or MIP.

The multi-objective problem can be solved in several different ways.

1) Create one measure, You can add three numbers, with weights. for example, you can create a measure, 20% of emission + 40% of time + 40% of the cost. and then Minimize the measure.

2) Set two of them as constraints and minimize one. For example, limit the amount of emission. Total emission should be less than a certain amount. And total cost should be less than $5000. and Minimize the travel time.

3) Find Pareto optimal solutions. (Find Efficiency frontier) Find solutions that are not dominated by any other solutions. Let the decision-maker to choose the solution.

There are a lot more in detail. Take a course or read a book in "Multi-Objective Optimization"

Answer 2

I suggest to start with the classical TSP formulation using $x_{ij}$ variables that are 1 if you go to city $j$ directly after city $i$ and then add the constraints that $x_{ij} = B_{ij}+F_{ij}+T_{ij}$ for all $i,j$. This allows you to to use all standard TSP machinery (e.g. sub-tour elimination constraints) via the $x_{ij}$ variables, without having to overcomplicate your model.

Answer 3

As basically a variant to what Rolf van Lieshout proposed, you could also add another index to your standard TSP variable: $x^t_{ij}$ where $t$ is the transport mode $t \in \{B, T, F\}$. You basically add $\sum_{t \in T}$ to most of your TSP constraints and of course need to limit the potentially chosen arcs between each city to one: $\sum_{t \in T}\sum_{i,j \in A} x^t_{ij} \le 1, \forall i,j \in A$. The basics of the TSP do not change with adding multiple arcs between cities.

Answer 4

I think all of the above-suggested models (by You, S. Phil Kim, Rolf van Lieshout, lvenhofen) have same number of nodes and arcs, correctly representing the problem to be modeled. However, one can reduce the number of variables as well as constraints in these models by representing either of 𝐵𝑖𝑗,𝐹𝑖𝑗,𝑇𝑖𝑗 binary variables in terms of other two variables, i.e., 𝐵𝑖𝑗 / 𝐹𝑖𝑗 / 𝑇𝑖𝑗 = 1 - (𝐹𝑖𝑗 / 𝑇𝑖𝑗 / 𝐵𝑖𝑗 + 𝑇𝑖𝑗 / 𝐵𝑖𝑗 / 𝐹𝑖𝑗), respectively. This might help you speed up the computations.

A multi (many) -objective optimization problem has 2 or 3 (>3) conflicting objectives, respectively. Hence, to model it as a multi-objective problem, first, one needs to identify the nature of these objective functions. If they are conflicting in nature, then you could solve them using MOEAs such as NSGA-II/III, MOEA-D, SPEA-R, etc. If the objectives are non-conflicting, the scalarization technique could be used, i.e., objectives could be combined using weights (as suggested by S. Phil Kim) but these weights need to be tuned. Intuitively, the objective functions to minimize time and cost shall be correlated (non-conflicting).

From my past experience, solving a single-objective NP-hard combinatorial optimization problem using Genetic Algorithms requires a lot of customizations, let alone solving this difficult version of TSP using MOEAs. Examples of such customizations are:

1. enhanced initialization, i.e., to generate at least one feasible solution in the initial population instead of all randomized ones,

2. retaining poor/infeasible solutions to maintain diversity in the population,

3. enhanced crossover/mutation operators,

4. infeasibility repair operators, etc.

Some useful articles for such customizations are:

1. J. E. Beasley, P. C. Chu, A genetic algorithm for the set covering problem, European journal of operational research 94 (2) (1996) 392–404.

2. D. Aggarwal, D. K. Saxena, T. Bäck, M. Emmerich, Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method, arXiv:2003.03792 [cs.NE] (Unpublished).

Answer 5

Your problem can be modeled in a different way that the one you proposed above, by following a set-based modeling approach instead of the classical Boolean modeling approach. This is a modeling approach offered by LocalSolver, a new kind of solver, different from traditional MILP solvers. Please note that LocalSolver is a commercial software. Nevertheless, it is free for faculty and students.

Below is the code snippet to model the classical TSP problem in Python:

    # Open the optimization model
    model = ls.model

    # List variable: cities[i] is the index of the ith city in the tour
    cities = model.list(nb_cities) 

    # Constraint: all cities must be visited
    model.constraint(model.count(cities) == nb_cities)

    # Array to store the distance matrix
    distance_array = model.array(distance_weight)

    # Objective: minimize the total traveled distance
    dist_selector = model.lambda_function(
        lambda i: model.at(distance_array, cities[i-1], cities[i]))
    obj = (model.sum(model.range(1, nb_cities), dist_selector)
        + model.at(distance_array, cities[nb_cities - 1], cities[0]))
    model.minimize(obj)

    # Close the optimization model
    model.close()

The complete code, as well as the corresponding codes for Java, C#, C++ are given here: https://www.localsolver.com/docs/last/exampletour/tsp.html. Having followed this modeling approach, LocalSolver finds quality solutions (optimality gap less than 1%) in a few minutes on a standard computer for TSP instances with 1,000 cities.

For an introduction to set/list-based modeling approach for combinatorial optimization, have a look to https://www.localsolver.com/docs/last/advancedfeatures/collectionvariables.html.