Optimising Routes

[Minty]

I have an interesting query involving moving vehicles around and optimising the drivers over those routes.
I'm not sure this is even a sensible process to try and manipulate in Access but I thought I would ask as there are some very clever people in here

Given the following data what would be the most efficient way to carry out the trips - ultimately there aren't enough movements between the various sites for a perfect solution, but what would minimise the amount of "dead end" trips.
Obviously a car can carry up to 4 other drivers to another site whilst making the trip.

From Postcode	To Postcode	No of Cars
HP11 1DD	SL2 5DR	6​
TW8 0EX	SL2 5DR	6​
SL2 5DR	RG4 8UA	5​
WD25 8HL	SL2 5DR	5​
SL2 5DR	WD3 8XD	4​
SL2 5DR	TW8 0EX	4​
SL1 5QA	SL2 5DR	3​
HA4 0LN	SL2 5DR	3​
WD3 8XD	SL1 5QA	3​
WD3 8XD	WD19 4BY	2​
WD3 8XD	WD25 8HL	2​
HP7 9PN	SL2 5DR	2​
HP11 1DD	AL1 1XB	2​
WD25 8HL	HP7 9PN	2​
WD25 8HL	TW8 0EX	2​
WD3 8XD	TW8 0EX	1​
SL1 5QA	TW2 5NT	1​
HA4 0LN	HP7 9PN	1​
NW9 0EW	WD25 8HL	1​
RG4 8UA	SL1 5QA	1​
SL1 5QA	HP7 9PN	1​
HP7 9PN	WD25 8HL	1​
SL2 5DR	WD19 4BY	1​
SL2 5DR	HP11 1BH	1​
WD25 8HL	WD3 8XD	1​
AL1 1XB	TW2 5NT	1​
WD3 8XD	SL2 5DR	1​
TW2 5NT	RG4 8UA	1​
TW2 5NT	WD25 8HL	1​
TW8 0EX	HP7 9PN	1​
TW8 0EX	WD25 8HL	1​
WD19 4BY	SL2 5DR	1​
WD3 8XD	AL1 1XB	1​
SL1 5QA	TW8 0EX	1​

There is a further twist that some of the postcode destinations are not far from each other, but that's a level of complexity to be looked at later.

Anyone have any techniques to apply, I'm suspecting this might be a @MajP type of hierarchy thing.
Maybe a treeview output with the branches representing the journey's ?
Presentation is a consideration as well.

 

[NauticalGent]

Seems to me if there were a way to leverage Google Maps, with the desired route settings, the vast amount of heavy lifting would be done there...

 

[Minty]

You can get google to do a shortest route between locations by either mileage or time, but this is more to do with limiting the number of drivers required to get everything moved over the course of a day.

So you could start with 5 drivers in SL2 5DR, use them to move 5 vehicles to RG4 8UA bring them all back in the single vehicle that needs moving in that direction (RG4 to SL2) and then use 4 of them to move the 4 vehicles from SL2 to TW8, this minimises the wasted journey or leaving a driver to get the train/bus back from that site to his next job.
There are then 8 vehicles need moving from TW8 to various locations 6 of which are back to SL2...

I didn't say it was easy....

 

[NauticalGent]

I didn't say it was easy....

No sir you didn't and it sure as hell isn't! This is going to take some serious "Kung Fu"

 

[MajP]

I am not sure I understand exactly what you want to optimize, but this may require an optimization algorithm. I have shown quite a few. See the traveling salesman problem which is an NP hard problem. That answers the shortest route to visit all cities.

School timetable - how to automate its creation?

In an ideal world, your school timetable will be based on the following conditions all teachers are full time each teacher always teaches in their own classroom there are sufficient specialist classrooms for each subject no classroom is ever required for other non-teaching purposes each teacher...

www.access-programmers.co.uk

Can you explain the optimization and constraints?

 

[MajP]

FYI, sometimes a guaranteed optimal solution is extremely hard to formulate, but a heuristic can provide a very good solution and far easier to formulate. That definitely does not mean easy. My TSP uses a three opt swap and flying bridge formulation. It took days for me to code. A true optimal solution would require a linear programming tool which is unlikely you could code.

 

[Minty]

I am not sure I understand exactly what you want to optimize, but this may require an optimization algorithm. I have shown quite a few. See the traveling salesman problem which is an NP hard problem. That answers the shortest route to visit all cities.

School timetable - how to automate its creation?

In an ideal world, your school timetable will be based on the following conditions all teachers are full time each teacher always teaches in their own classroom there are sufficient specialist classrooms for each subject no classroom is ever required for other non-teaching purposes each teacher...

www.access-programmers.co.uk

Can you explain the optimization and constraints?

I'll try but it's a bit woolie.

The constraints are minimal, with a maximum number of drivers of 15 on a given day (this can vary), and a maximum number of jobs per driver is say 8 due to driving time limits. We do have mileages and travel times available, but they aren't taken into consideration at the planning stage.

The optimization is all about efficiency of driver movements, e.g. the minimum amount of one-way journeys, combined with using as small a number of drivers as possible.

I appreciate that this is very broad and is currently carried out manually with lots of bits of paper, a pencil and a very well used eraser, and someone with a lot of experience in doing it.
It may not be solvable in a sensible manner in code that can run efficiently.

I am thinking that something that makes an initial stab at a "top level" answer may be sufficient to start the ball rolling.
In other words, a process to provide a rough initial starting point for a human to then refine based on other factors which aren't quantifiable within the existing data. (Bus and train routes to get drivers back to another pick up point etc.)

 

[The_Doc_Man]

There is another question to consider. We've had several such questions on this forum over the years. Some of them deal with coordinates of the center of each postal code (for USA, ZIP code). But thinking of driving around Boston and New Orleans, I remember another factor... basically "You can't get there from here."

Because of one-way streets and limited-access highways, there are certain areas in both cities I named for which it is not legal to make a left turn for maybe as much as a quarter-mile. Tulane Avenue in New Orleans is notorious for that. Getting from the north portion to the south portion of Taft Parkway (due to an intervening interstate highway with no close overpass or underpass interchanges) is another tricky bit of navigation. I'm sure that many of you know other examples.

When looking at map data, be sure to include information on available routes and be prepared to work with recursion. This WILL be a case for which a "divide and conquer" approach will be paramount. I might consider a "preferred short path" feature for every geographically adjacent zone. I.e. if area A has borders with areas B, C, and D, find the best routes for A-B, A-C, and A-D. Then for things that are separated by one intervening zone, you can do a routine using the adjacency routes. But you might want to consider long-distance priorities, such as routines that are many zones apart, for which a short route isn't optimum if a limited access roadway exists going in the right general direction. I'm sure that when you use the Google Maps "Find my route" feature, they do something like that. I would bet that they probably look for the longest "legs" first.

 

[GPGeorge]

Speaking of Google Maps, maybe they offer an API that you could incorporate to work with their Google Maps data to enhance your solution.
While that sounds like it might increase the complexity of the solution, it is entirely possible that in the end, the results could be worth it.

 

[Minty]

@The_Doc_Man In this instance the actual route driven is immaterial, they drive them frequently many times a week, it's the scheduling of the order of the journeys, so collating the same moves together with an onward or return journey if possible.

Today, Driver A does Journey No1 1st, then journey No4 second then Journey No2 3rd etc. etc.
That's where the linear approach suggested by MajP might well comes in.

It's a bit like thinking ahead in chess moves, but with less possibilities.

 

[Gasman]

There is another question to consider. We've had several such questions on this forum over the years. Some of them deal with coordinates of the center of each postal code (for USA, ZIP code). But thinking of driving around Boston and New Orleans, I remember another factor... basically "You can't get there from here."

Because of one-way streets and limited-access highways, there are certain areas in both cities I named for which it is not legal to make a left turn for maybe as much as a quarter-mile. Tulane Avenue in New Orleans is notorious for that. Getting from the north portion to the south portion of Taft Parkway (due to an intervening interstate highway with no close overpass or underpass interchanges) is another tricky bit of navigation. I'm sure that many of you know other examples.

When looking at map data, be sure to include information on available routes and be prepared to work with recursion. This WILL be a case for which a "divide and conquer" approach will be paramount. I might consider a "preferred short path" feature for every geographically adjacent zone. I.e. if area A has borders with areas B, C, and D, find the best routes for A-B, A-C, and A-D. Then for things that are separated by one intervening zone, you can do a routine using the adjacency routes. But you might want to consider long-distance priorities, such as routines that are many zones apart, for which a short route isn't optimum if a limited access roadway exists going in the right general direction. I'm sure that when you use the Google Maps "Find my route" feature, they do something like that. I would bet that they probably look for the longest "legs" first.

I use Google Maps to find new addresses for my community work and how to get there.
On some occasions, it has directed me driving up lanes, that are not passable by cars?

 

[AccessBlaster]

"An estimated 90% of the turns made by UPS delivery trucks are right turns, and that's intentional, according to the Washington Post. Left turns are seen as inefficient, because they leave trucks sitting in traffic longer."

 

[MajP]

To make sure I am reading this correct. On the first line there are 6 cars at HP11 1DD and must go to SL2 5DR.
1. When the 15 or so drivers show up how do they get to the first starting location? Lets say 6 drivers go to HP11 1DD. Do they take their own POV or transportation to get at the starting point or can we assume they just show up and it does not really change the calculation? If you have to put 15 drivers in a van and take them to the starting locations does that have to be factored?
2. What happens at a dead end? There are a lot of 1 car deliveries. Do you normally send two cars in this case where one driver delivers the car and a second takes them to the next location? If a driver gets stranded what happens? Van picks them up? Take a bus?

3. I assume that amount of dead ends is what you initially want to minimize, but I bet you would want to also get a shortest path. If you had two solutions with 2 dead ends you would take the solution where overall distance is the least. These kind of problems are usually formulated by weighting the two minimizations. So the best solution might be some weighted average of (p) * Number Dead Ends + (1-p) * total distance

My first thought is that this is a graduate level optimization requiring a custom algorithm. It does not fall into any common algorithms I can think of.
I would be interested in how you lay this out now, but I imagine it is a bear. What does the final plan look like.
1. My first attempt would be to digitize the manual process. Make a nice gui to make doing manual selections easy. Show you what is complete, what is remaining, how it was moved and let you update with simple clicking. Do you have this already.
2. Same time I would build the data structure to support any future alogritm.
See this discussion on graph theory and how you would map it.

Route Planning - shortest path

I'm trying to get my head around using the following data to create the shortest route between 2 places in a map using VBA in either excel or access. ID Name Connection 1 Connection 2 1 Location1 2 2 Location2 3 4 3 Location3 2 4 Location4 2 5 5 Location5 3 5 So...

www.access-programmers.co.uk

3. Once the structure exists, I think I can automate that to get a feasible solution. Deliver all vehicles using the available drivers and no more than 8 trips per driver.
This data structure would then support displaying the movements and identifying dead ends.
4. A lot of these graph theory algorithms are "spanning" algorithms. They start from the beginning and span to next location. If there is a better solution for moving to a node than that path is choosen. Many of these look forward a few nodes and then roll back if a constraint is reached.

I would have to play with this but think I could get a feasible solution and use some basic rules to get a good feasible solution. More importantly I would think is providing the GUI to manually update based on real world constraints that you could never code (John has to be done by noon, Mike cannot drive a stick shift, Location X has to be first because closing early.)

 

[Minty]

Great analysis @MajP , and a lot of the questions are ones I have gone back to the client with, but also some other ones I hadn't thought of.
As is often the case with these type of complex tasks, trying to get under the skin of the manual process is key to trying to understand the best approach.

The GUI is another aspect we are working on at the moment, so the initial step is to just try and simplify the paper process as you described, so we have a couple of side by side subforms that interact and display all the un-scheduled jobs one side and any related (by postcode) jobs on the other side. They select a driver, and a schedule number, they can do this on either list. I have a third subform that displays the scheduled drivers and jobs as a summary (and thinking about it I should add the postcodes to that list as another visual aid), and they can click on the listed job to bring up on the main list if they need to edit things.
Both lists can either hide or display already scheduled jobs
This is significantly quicker than searching through print outs.

Having looked at an existing successful days planning, the initial results look as if the chaining together of 5-6 jobs per driver is how the best results are achieved. This means (rather obviously) that a potential dead end is their last job and they only have to make one public transport return or get picked up by a colleague. The ideal would be to return to the starting point as the last job.
I believe the drivers make their own way to a starting location.

Thanks for delving into the process, and I will look at the sample for the shortest distance to see if that can assist.

 

[MsAccessNL]

I have made a shortest route dispatch system for a courier business in Amsterdam. Solving the traveling salesman problem with vba and the googe api, took my a lot of time, but was really fun making it. For me it is still not clear what your business is doing. (I have not read all the posts). Is het a car rental?

 

[gemma-the-husky]

They sell commercial logistics packs with stuff like this for quite a lot.

It's maybe another exercise in linear programming. Find a solution, and then try to change settings, and improve the efficiency of the solution.

 

[gemma-the-husky]

I once wrote (turbo pascal) a programme to try to evaluate the best football manager team. You estimated how many points each player might earn in a season, and then the programme tried to find the best team for the money. I don't think I have the code any more unfortunately.

 

[jdraw]

Minty,

In the past, following threads given here and elsewhere, I have asked MajP for advice on a Constraint Satisfaction Problem. He graciously advised me of the type of issue I was reviewing and assured me of some of the complexities I could expect in very short time if the number of variables grew. Since then I have consumed several youtube videos and have convinced myself that the subject area generally - combinatorics, optimization, satisfaction...- is overwhelming. However, here is one youtube video based on the Traveling Salesman Problem that helps make several concepts and complexity somewhat understandable. It isn't necessarily an answer to your question, but it will give you an appreciation of the subject area.

 

[Minty]

It's maybe another exercise in linear programming. Find a solution, and then try to change settings, and improve the efficiency of the solution.

This seems the most promising route to go.
I have made a simple routine that creates "chains" of routes by looking for any unscheduled routes with the From postcode that matches the To postcode, it marks the chosen with a schedule number and used, then continues. We can count up the number of new starting points as a guide to how efficient it was.

Next stage is to then loop through all the possible starting codes, and run the same routine to see if altering the starting point gives dramatically different results (I'm sure it will but not sure how much of a difference). If it does, then we can try and identify the best starting point either by brute force (for testing purposes as it might take a while), or manually testing and progress with that.

I'll report back once we've compared results with the human created version to see if it's better, worse or similar.

 

[MsAccessNL]

Excel has also a “solver” where you can run (algorithms. I can take a look if i can adopt my courier algorithm, but then i have to know all your restraints. They are not totally clear to me.

Tip: I reversed engineered a lot of shortest path code from JavaScript into vba. I didn’t knew at that time that i could could run js inside the website control. Another advantage of this approach is that the code could run asynchronous.

Tip: Using the exact street adress or longitude/latitudegive you much better result.

Look at the factorial math formula. The amount of possible combinations is exponential. (Meaning your code will take a long time).

Good luck.