1
$\begingroup$

In a public transportation network each stop has an assigned zone. The price of a trip depends on the number of adjacent zones that the user touches during a given trip. If the user touches two adjacent zones it must pay a Z2 title, and it can travel with that title during 1 hour. The time to travel (and price) increases as the number x in Zx also increases.

Imagine the following trip: The user starts at stop A (zone B6) at 16:00h and it arrives at location B (zone B1) at 16:30h. Because the user only touched two adjancent zones (B6 and B1) and the trip took less than 1 hour to complete, the user only pays a Z2 title (the minimum that is possible).

Now imagine a more complex trip: The user starts at stop A (zone B6) at 16:00h, travels to location B (zone B1) and it arrives at 17:00h, and finally it travels to location C (zone B1) and it arrives at 17:30h. On this case the user could pay a Z2 title to travel between 16:00h(Location A) and 17:00h(Location B) and another Z2 title to travel between 17:00h(Location B) and 17:30h(Location C) (2xZ2=2x1€=2€) or it could buy a Z3 title which allows him/her to travel 2 hours between three adjacent zones and it costs 1.50€. In this case the Z3 title would be a better choice.

This looks like a combinatorial optimization problem. I need to combine all trips during one day to find the minimum price. I'm here to ask for a starting point. Which algorithm should I look for to begin solving this problem? Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Seems like a multiobjective shortest path problem. You can model each zone with vertices and edges with vectoral weights. Each weight consists of a token and a time variable. If you come up with a scalar comparison function that fits for your needs, i.e. can tell which edge is better to choose considering their weights, the Slater optimal path can be found by simple shortest path algorithms such as Dijkstra's. But if you have to find the Pareto optimal path, which is the overall trip's cost, then you should look for more complex algorithms since the problem is NP-complete. $\endgroup$ – Husrev Jan 20 '18 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.