CODEWITHSUNDEEP
algorithm
alexibbb
alexibbb

Reputation: 103

Algorithm to find the best itinerary for traversing cities in a certain number of days

I have a list of cities, and the distances between two neighbouring cities. Given a start and end city, I need to find the optimal route between them, given the constraint that it must be completed within a certain number of days.

What would be the algorithm that can achieve this?

EDIT: Example would be you start in city1 and end in city7. You have the distance between this and the previous city. You have 2 days to complete the journey, and you want the distances per day to be approximately equal. Also the route is defined, i.e. you're going through the cities in the order already defined, the only variation being which cities and how many you pass per day.

City1, 0 City2, 3 City3, 4 City4, 1 City5, 4 City6, 3 City7, 2

Upvotes: 1

Views: 332

Answers (1)

John Scattergood
John Scattergood

Reputation: 1042

This is a constrained version of the Traveling Salesman Problem (TSP): https://en.m.wikipedia.org/wiki/Travelling_salesman_problem

Here is a paper that describes an algorithm for the time constrained version:

http://pubsonline.informs.org/doi/pdf/10.1287/opre.31.5.938

The authors use a branch and bound approach to solving the problem.

Upvotes: 2

Related Questions