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.