Conquering all metro stations using Pyomo

Metro-hopping refers to the act of traveling on a metro system, visiting different stations in a quick and efficient manner. It is like a game or challenge where the goal is to visit as many stations as possible in a short amount of time. Metro-hopping can be seen as an adventure or a way to explore different parts of a city. It is a fun and exciting activity for those who enjoy public transportation and want to experience the thrill of navigating through a metro network.

I was thinking about how to use mathematical optimization to do this as fast as possible. For this reason, I chose Budapest's metro network (not hard to guess why).

The idea is to start from one station and visit all stations in a continious tour (no need to return to the starting station).

Mathematical formulation

1. Defines the objective function as the total travelled distance
2. Just one stations should be selected as the starting station
3. At each step k, only one move should happen
4. out_ik shows if it moves out of node i in step k
5. ent_ik shows if it moves into the node i in step k
6. Every node should be either starting node or should be visited at ant step
7. we can go out of node i in step k only if we entered the same node in step k-1
8. in step k=1 we go out of starting node

• U_ijk is a binary variable indicating the move from node i to node j in step k
• Start_i is a binary variable indicating if the node i is the starting node
• out_ik a real variable indicating if we move out of node i in step k
• ent_ik a real variable indicating if we move into node i in step k
• i,j are the set of nodes
• k is the set of steps

Pyomo Code

Results

There are several observations in this problem :

• This is not a TSP model. Some nodes will be visited more than once. This will stop us from using famous MTZ formulation
• The number of required steps for creating the countinious tour is not know in advance. Considering a small k will result in infeasibility and considering it so big will cause computation burden.
• The starting point is important in finding the optimal shortest path problem (it's better to be determined by the model)
• Equation 3 can be expressed as follows:
• forall k <=N ----->. sum_ij Uijk = 1
• forall k > N ----->. sum_ij Uijk <= 1
• This is because we already know that at least N steps are required for creating this tour

The Pyomo code is available on the?Github?, you can support this newsletter by giving a star to it.