CODEWITHSUNDEEP
algorithmdijkstratraveling-salesman
Kunal Shrivastava
Kunal Shrivastava

Reputation: 612

Route for appointment locations based on distance and appointment time

I want to develop an algorithm which taken in location and appointment times of different places a person needs to visit starting from his/her office. After completing all the appointment visits, this person must come back to the office. I want to plan a route for him/her that covers all the appointments in such a way that:

My question is open-ended. I know that if I just want to take the distance into account for constructing a route, this fits directly into the Traveling Salesman Problem. But, I also want to take the appointment time into account. I am new to graphs and I was wondering if this problem fits better into some other algorithm that I am not aware of. If not, I am looking for suggestions for modifying the TSP algorithm to consider these two parameters.

While thinking about this problem, I thought about how I would implement Dijkstra for finding a route. I am aware that this is a completely different problem than TSP. But, how do you think I can combine two parameters(distance and appointment time) to compare two nodes in my priority queue ADT for Dijkstra.

Probably, these two problems require different questions but I feel that this is a common problem. I am looking for suggestions about approaching these graph problems where there are two factors that need to be considered. How can I take two parameters and combine them into one, so that I can compare two nodes?

Upvotes: 0

Views: 118

Answers (1)

Chris
Chris

Reputation: 959

Assuming you need to be on time for an appointment and not early, then you can start with a fully connected graph and then remove edges between nodes if they are too far apart, according to their appointment times.

For example if Node A has a time of 10:00 and node B has a time of 11:00 and the shortest distance between them is over 1 hour, then you can trim this edge.

This also includes trimming edge(A,B) if Node A has an appointment time after node B.

After this you only need to find the shortest hamiltonian cycle - which is TSP.

Edit: To answer your question directly: There is no need to account for the appointment time in the TSP part of the problem. Simply setup the graph (as described above) and then run a TSP algorithm.

Upvotes: 1

Related Questions