Optimizing a schedule - via brute force?

Hi all,

Partially for helping, partially for fun, I'm trying to optimise one of my relative's working schedule. Her work consists on teaching her students around the city. I'm trying to make RStudio propose a few student schedules that minimize the amount of time she spends on the road. I haven't written any code so far, but I'm trying to come up with the flow of the script.

Every day she starts her trip from home. After 45 or 60 minutes of teaching, she moves to the next student's location. Last, she returns home. She works 5 days per week, and depending on the day she can dedicate 3, 4 or 5 hours to her work. In total, she has 15 students and each has to get one lesson per week.

I can get from google maps a matrix with the time it takes to travel between each pair of students, and each student to home. Then, if I add to the travel time the time spent teaching to get the total time it takes to move to one spot to the next.

So far, I have thought on some brute force method based on permutations of the students order. My idea is to create vector permutations of weekly options. If "x" is home and "A, B, C,..." each student, one of the vectors would look like "x,A,B,C,x,D,E,x,..." (note x marks the initial point and the end of the day). By using the time matrix previously created, I could calculate the total time spent if she chose that order of students. Last, I would simply pick the vector that gave the lowest time.

I think however this is probably a terrible strategy due to the high number of combinations... It could be reduced by limiting the amount of students per day or sorting out unfeasible combinations (e.g. student B can only be taught on Thursday). Would you recommend any better strategy? I feel this might be a common problem many people face, but after reading between lines about the "Travelling salesman problem with time constraints", I'm worried this problem might be much bigger than I initially thought.

Thanks for the input!
Enrique

This is the Traveling Salesman

I just searched CRAN for you now
https://cran.r-project.org/web/packages/TSP/index.html

2 Likes

This is a class of optimization problem known as the traveling salesman problem. A search on rseek will provide many resources, such as the TSP package.

Given the notorious difficulty of nailing down an optimum solution, combined with the uncertainty around traffic on any given date, it is best to adopt a satisficing solution over searching for an optimal solution.

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.

If you have a query related to it or one of the replies, start a new topic and refer back with a link.