Optimising Routes

[Minty]

As mentioned in a previous post, this isn't really about the shortest route, more the efficient use of the available drivers, which is a quite difficult to quantify.

I haven't had a chance to play around with the starting options yet but typically if there are 100 movements on a day there are approximately 40 different actual routes, and only around 10-12 starting postcodes, and a similar number of destination postcodes. So to work out all the starting possibilities isn't a huge number of iterations. It may well be that checking all of them gives us a very good initial working point.

 

[The_Doc_Man]

There is a hair's breadth of difference most of the time, but if you trying to minimize the DRIVER's time usage, queueing theory says that you assign the longest drives first from among the drivers you could reasonably assign to the same starting point.

 

[jdraw]

Minty,
Do you have any more info?

You have these distinct FromPostalCodes:

pc
AL1 1XB
HA4 0LN
HP11 1DD
HP7 9PN
NW9 0EW
RG4 8UA
SL1 5QA
SL2 5DR
TW2 5NT
TW8 0EX
WD19 4BY
WD25 8HL
WD3 8XD

And these distinct TOPostalCodes:

pc
AL1 1XB
HP11 1BH
HP7 9PN
RG4 8UA
SL1 5QA
SL2 5DR
TW2 5NT
TW8 0EX
WD19 4BY
WD25 8HL
WD3 8XD

And these distinct postal codes over all:

pc
AL1 1XB
HA4 0LN
HP11 1BH
HP11 1DD
HP7 9PN
NW9 0EW
RG4 8UA
SL1 5QA
SL2 5DR
TW2 5NT
TW8 0EX
WD19 4BY
WD25 8HL
WD3 8XD

Can you tell us ore about "100 movements on a day there are approximately 40 different actual routes,"?
And exactly what the No of Cars means?

 

[MajP]

As mentioned in a previous post, this isn't really about the shortest route, more the efficient use of the available drivers, which is a quite difficult to quantify.

People should really give the TSP a rest here as a potential solution. Your problem is only roughly related to a TSP this is more a traditional spanning tree or shortest path problem through a directed graph. However, like the TSP an exact solution for this may be extremely difficult to formulate. Graph theory algorithms can likely make a reasonable heuristic giving good solutions. For someone who has linear programming experience I think this would be extremely hard to formulate as an LP (if even possible) and you would probably have to write code to write your formulations prior to passing to an LP solver. I think if you look at my Djikstra algorithm I have most of the data structure components to formulate something that can give a feasible solution. Most likely provide simple heuristics like nearest neighbor to get a reasonable solution. Then from there consider improving algorithms.

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

See if I understand the setup
1. I believe it is a multi objective problem
Minimize number of dead ends (stranded drivers)
While minimizing total distance travel
Also it has to be feasible so the total vehicles to move <= Number of drivers * 8 trips
2. Contraints
Driver trips <= 8
3. Inputs. Number of drivers, routes to move number of vehicles.

Things that complicate this is that you can piggyback drivers if a driver arrives at a location with N vechicles required to arrive but some number <N that are leaving.

I will give this a try to formulate this using a spanning algorithm with possibly improving algorithms

Normally you want to do these types of problems using arrays for speed. But I think you need to store a lot of information and inputs so I would do it as a full oop implementation.
The data structure do to this represents a directed graph storing Vertices and Edges. In this case the Vertex are the locations and the edges are the paths between the location.

Class Edge:
--LocationStart (points to a vertex)
--LocationEnd (pointer to a vertex)
--NumberVehicles

Class Edges
-- CollectionEdges - collection class of edges

Class Vertex (Location, Postcode)
--Vertex Name (postcode name)
--TotalCarsToShip (not really needed for the algorithm but store anyways)
--CarsLeftToShip (running count)
--CarsLeftToArrive (runnimgCount)
--PiggyBacks (number of drivers awaiting for piggyback)
--ArrivalEdges (collection of arrival information)

Class Vertices
--Collection class of vertex

Class RoutingProblem
-- AllEdges
--AllVertices
--AllShipments
methods in here to drive the problem

Class Shipment
-DriverID
-VertexStart
-VertextStop
-DriverOrPiggyback

Class Shipments
custom collection recording all movements


I am unclear on starting locations put until that is clear I will assume a driver can start anywhere, but I do think this is important.
Here is an extremely rough algorithm, but I think once I start playing with it I can figure out how to iterate it. After each shipment update the Shipments class which holds the record of all movements to report the plan.

1. Pick a driver and assign starting point
2. Span edges picking nearest neighbor to pick next route. If nearest neighbor is a dead end pick the next nearest neighbor
decrease cars left to ship by 1
decrease cars left to arrive at next node by 1
update the edges number of vehicles by 1
3. "Move" to next vertex you selected
4. Verify that Number to ship >= number to arrive. If Number to ship <= to number to arrive leave driver at node by
updating piggybacks by 1
4a. If you left a piggyback then start routing next driver
4b. if no piggyback left then continue with that driver
5. If the next node has piggybacks determine if the number to left to ship - piggybacks <= Number to arrive (then assign a piggyback) and pick next node. Now next node has to have driver + piggybacks <= Number to ship or it is a dead end.
This gets really complicated in my opinion
Assume Vertex A has 3 vehicles to ship but 5 arriving. So there needs to be 2 piggybacks. There is no easy algorithm to figure out if 3 people (a driver and 2 piggybacks) go to B or if 2 go to B (driver and 1 piggyback) and 2 go to C (driver and 1 piggyback) or all the other possibilities.
I think I would apply the rule if there is a piggyback take them immediately. Then let the last driver take additional.

Once a drive completes 8 trips they are complete
To add complexity I think I would try to code a rollback. If a driver hits a dead end, roll back one vertex and try another path. If all those are exhausted roll back two vertices and span from there. Keep doing until all conditions exhausted and pick the best of the dead end solutions.
Similar to how the dijkstra works.

Questions
1. Is a dead end only when a driver gets stranded or does a driver have to make it back to the start?
2. Can the drivers start anywhere or is there a cost? If you have to drive them to the starts then you may want to send large groups to a location that has a lot to deliver.

After typing this I think you could leverage the flory warshall algorithm i demo here

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

You could then start with all potential 8 trip (and less) tours. This would have every start and every path to every end point. Then you could rank these by distance. You send a driver on the best tour. Once all vehicles are delivered from a location all tours that include that location get removed from consideration. I still have to wrap my head around planning for piggybacking to next location, but I think that is a good start.

 

[MajP]

@Minty,
I played with this an thought I got a pretty good solution, but after a very promising start I think I hit a snag

IMO this is a graph theory problem and modeled like any Directed Graph.
In Graph Theory. You model Vertices and Edges. Vertices are also called nodes, Edges are also called links or arcs. The cost to move from one Vertices to the next across an edge is called the Edge Weight. Sometimes this is distance, but you can model other things like financial decisions that are not physical distance. Could be dollars, voltage, gallons, etc.

Here is a graph.

You would model your Post Codes as nodes, and in your case your Edges could hold both distance and the required number of vehicles to ship from a post code to another. This is called a Directed Graph because things can only move in certain directions from certain nodes. An undirected graph means you can move to any Node in any direction.
(The TSP is modeled as an undirected graph because you can move from any city back or forth. In fact it is a Complete Graph because all nodes can connect to every other node)
The above graph is also called Cyclical. You can create a cycle. You can go A-B-C-D-E-A or A-C-E-A. Two nodes can make a cycle if there was an Edge A-B and an Edge B-A then A-B-A would cycle.

Most basic algorithms you start off with deal with DAG (Directed Acyclic Graph), or solutions without cycles.

As I said I had a lot of this code already. As a test I modeled your data and put in some distances between the Vertices.

qryShippingVertices qryShippingVertices

VertexID	VertexName
1​	AL1 1XB
2​	HA4 0LN
3​	HP11 1BH
4​	HP11 1DD
5​	HP7 9PN
6​	NW9 0EW
7​	RG4 8UA
8​	SL1 5QA
9​	SL2 5DR
10​	TW2 5NT
11​	TW8 0EX
12​	WD19 4BY
13​	WD25 8HL
14​	WD3 8XD

The Edges show the Star post code, end postcode, the distance (edge weight) and number of cars to deliver
tblCarShippingEdges

EdgeID	StartVertex	EndVertex	EdgeWeight	CarsToDeliver
1​	14​	1​	25​	1​
2​	4​	1​	5​	2​
3​	9​	3​	20​	1​
4​	8​	5​	15​	1​
5​	2​	5​	5​	1​
6​	13​	5​	25​	2​
7​	11​	5​	25​	1​
8​	10​	7​	20​	1​
9​	9​	7​	15​	5​
10​	7​	8​	10​	1​
11​	14​	8​	10​	3​
12​	8​	9​	10​	3​
13​	11​	9​	20​	6​
14​	13​	9​	25​	5​
15​	5​	9​	10​	2​
16​	4​	9​	5​	6​
17​	2​	9​	5​	3​
18​	14​	9​	30​	1​
19​	12​	9​	25​	1​
20​	8​	10​	15​	1​
21​	1​	10​	5​	1​
22​	8​	11​	15​	1​
23​	9​	11​	15​	4​
24​	13​	11​	25​	2​
25​	14​	11​	25​	1​
26​	14​	12​	15​	2​
27​	9​	12​	20​	1​
28​	10​	13​	20​	1​
29​	11​	13​	25​	1​
30​	6​	13​	10​	1​
31​	5​	13​	10​	1​
32​	14​	13​	20​	2​
33​	9​	14​	15​	4​
34​	13​	14​	5​	1​

Using the above I can use the Djikstra code to find the shortest distance between any start and point. Not needed for your problem, except verifies I could import and model.
Examples

So since this is a directed graph. You can go from ALI1XB to HP111BH via Nodes 1,10,7,8,9,3 with a distance of 65.

By my thought was drivers can drive 8 legs. The most efficient routing is the shortest 8 leg route. Consider the ratio as the number cars moved by number of drivers. If a route exists were two drivers can move 16 cars then 16/2 = 8 and is a perfect choice. Or one driver moves 8. This number is reduced by any piggybacking or short routes.

1. I found all routes Acyclical from all starting points up to length 8. This is done using a Breadth First search of the graph. (not trivial). Some routes terminate early. Then allowed the user to assign Driver/s to the route picking the longest routes with the shortes length first.

Upper left are all the routes sorted by Trips length, then distance. Lower left are the detailed individual trips in that route. It shows how many vehicles required to ship from Node to Node. How many actually shipped for that trip on that path. If a piggyback was used, and Remaining to ship. The right shows all edges (trips) and totals.
2. You can pick the top route (best) or any other route and assign driver/s. I assign the longest shortest route 1 driver which will give 1 driver 8 deliveries (ratio of 8)
3. This updates the cars shipped per that path. If there is a "complete" edge (all required cars delivered), I remove all paths that include that edge. You can see 1408 potential paths to start.

4. After assigning 1 driver in the lower left you can see the details on how many vehicles delivered from each node on that path. To the right you can see the totals updated and in green completed deliveries. Once these completed Edges are removed from potential paths you can see only 452 remaining paths. There are only 7 paths with 9 nodes (8 trips) left.

 

[MajP]

5. If you assign more drivers that a node has vehichles on the path it will calculate the amount of vehicles delivered plus the piggybacks. The piggybacks reduce your ratio. 14 Vehicles delivered / 2 drivers = 7. This is equivalent to sending 2 drivers on a 7 trip path.

This just demonstrates in the lower left that it piggybacked a driver when there was not enough vehicles.

All of this was going great and I just kept going down the list picking the next best route. Remember each time a Node is complete it pulls it from all potential paths. You can see above after 2 assignments there are only 201 paths, but no more with 9 nodes (8 trips). The best next path can only deliver 7 vehicles.
Eventually doing this approach the only remaining paths were shorter and shorter. This is because there are a lot of nodes with only 1 vehicle and a few with 6.

This is where I think my logic failed. I realized this is not a DAG and in fact you want to be able to cycle to go back and forth between nodes with lots of vehicles. This will require a much more complicated (as if this was not enough) approach. Working with cyclical graph algorithms is really hard. I think I have an idea, but it would be a completely different approach.

Your thoughts.

 

[NauticalGent]

MajP, you are if anything, one impressive SOB...

 

[jdraw]

MajP,

Very impressive piece of work.

 

[Minty]

Hi MajP - that is mighty impressive, and a lot of work to boot.
I can provide mileages with the data, but I feel you have already spent way too long on this, unless you are at a loose end!

I have used a very simple process so far, I loop though each unique start or end post code and end up with a list schedule, this takes no account of mileages at the moment, but does indicate the best starting point to get the maximum chained journeys.

I can see how refining your method would give a much better fit for the best plan in the end.

I'll PM you with some further data but only if you want to play around with it a bit more, I can also send you some of the clients actual manually worked out routings/schedules for the same data. The worst case so far is nearly a 100 movements in a single day, so I'm intrigued to see how the various automated methods compare to the results from the human.

They do take account of the distance from a drivers home to the first job, and getting back, so that will have some bearing on it as well, and I don't currently have that data (or at least I don't think I do).

 

[MajP]

Hi MajP - that is mighty impressive, and a lot of work to boot.
I can provide mileages with the data, but I feel you have already spent way too long on this, unless you are at a loose end!

I will continue to play with this just out of curiosity. My degree included optimization and graph theory, but I only remember enough now to be dangerous or at least know that there exists a smart person out there that can address this.
I think this at least gives some ideas on potential ways to construct this problem and provide visualization to allow the user to make informed choices. It is far from providing a realistic solution.

I have used a very simple process so far, I loop though each unique start or end post code and end up with a list schedule, this takes no account of mileages at the moment, but does indicate the best starting point to get the maximum chained journeys.

I would be interested in your simple approach. As I said, I coded a breadth fist search from each starting point to get all possible paths "chains" up to 8 trips. That code is far from simple, but the basic classes already existed in my Shortest Path application.
Do your chains include cycles?

The good thing about my setup is that you can "what if" each step and see what the down stream effects are. My heuristic using the longest chain (no dead ends) of the shortest distance provides a local optimum. However that is the problem with most optimization problems. Each local choice impacts the overall solution. So you often have to pick a sub optimum choice to get a better overall solution.
Every time I "complete" a location it removes all other paths that included that location since there are no longer any cars to deliver at that location. So it may be smarter to start with a fewer node path like 7 trip path, but most nodes have more than 1 remaining car. This way you decrease the high count locations without removing a bunch of potential paths. Some form of this logic could be applied using the current design.

I think that is the strategy, because you have a few nodes with a lot of vehicles and a lot of nodes with few vehicles. What happens is that you quickly create "islands" where there are no longer any paths coming in, but there are a lot of vehicles still to deliver.

This is where the cycles could make this a thesis level problem. Assume there are locations A,B,C and from A-B there are 6 cars to deliver, B-A there are 6, and B-A has six.
2 drivers could do A-B-C-A-B-C-A-B- C and deliver 16 cars with no dead ends and maximizing their allowable trips. Somehow I need to account for these favorable, but that requires a completely different approach. You cannot find all potential paths with cycles, because that is infinite. I find the non cyclic paths and use that to pick a shipping plan.
If the cycles are considered then I think you need an algorithm that creates the plan as a path is found. This could work like a nearest neighbor algorithm. Start at a node and deliver one car to the neighbor with the most cars to deliver and update the amounts keep picking the next neighbor with the most cars to deliver. This would have to include a roll back feature so if you hit a dead end early you roll back to the next "highest" node and branch from there. As nodes are completed they are popped out of the search. This approach may help eliminate island because you are trying to deliver the high count nodes first. As the graph starts to even out with roughly equal amount of cars per node then the heuristic could switch back to my shortest path solution. Again the shortest path is really just a tie-breaker when you have equal length chains to pick from.
This is common with search algorithms in that you monitor the overall state of the graph and change the search or next choice logic as the overall solution progresses.

 

[MajP]

If anyone is interested in playing with this here it is. As I said this is far from producing a solution and is only academically interesting. It does provide some concepts. It is an exercise in VBA OOP there are lots of composite classes. And some of these classes reference themselves.

Looking at the data more it is clear I do not think a solution can be approached without cycling, so my initial stab does not get you very far. The initial approach did not include cycling (return to a previously visited location).

Looking at the data sorted by the number of vehicles to Deliver along an edge. There are a few edges with a lot ( 6 veh x 2, 5 x 2, 4 x 2, 3 x3)
then a lot of singles (19). You can see where cycling can help
TW8 OEX needs to deliver a lot of vehicles (6) to SL2 5DR and SL2 5DR needs to deliver 4 vehicles back to TW8 OEX. That cycle would greatly improve getting to a better solution.

subFrmEdgeCompletion subFrmEdgeCompletion

Start	End	Distance	To Deliver
HP11 1DD	SL2 5DR	5​	6​
TW8 0EX	SL2 5DR	20​	6​
SL2 5DR	RG4 8UA	15​	5​
WD25 8HL	SL2 5DR	25​	5​
SL2 5DR	TW8 0EX	15​	4​
SL2 5DR	WD3 8XD	15​	4​
WD3 8XD	SL1 5QA	10​	3​
SL1 5QA	SL2 5DR	10​	3​
HA4 0LN	SL2 5DR	5​	3​
HP11 1DD	AL1 1XB	5​	2​
WD25 8HL	HP7 9PN	25​	2​
HP7 9PN	SL2 5DR	10​	2​
WD25 8HL	TW8 0EX	25​	2​
WD3 8XD	WD19 4BY	15​	2​
WD3 8XD	WD25 8HL	20​	2​
WD3 8XD	AL1 1XB	25​	1​
SL2 5DR	HP11 1BH	20​	1​
HA4 0LN	HP7 9PN	5​	1​
SL1 5QA	HP7 9PN	15​	1​
TW8 0EX	HP7 9PN	25​	1​
TW2 5NT	RG4 8UA	20​	1​
RG4 8UA	SL1 5QA	10​	1​
WD19 4BY	SL2 5DR	25​	1​
WD3 8XD	SL2 5DR	30​	1​
SL1 5QA	TW2 5NT	15​	1​
AL1 1XB	TW2 5NT	5​	1​
SL1 5QA	TW8 0EX	15​	1​
WD3 8XD	TW8 0EX	25​	1​
SL2 5DR	WD19 4BY	20​	1​
TW2 5NT	WD25 8HL	20​	1​
HP7 9PN	WD25 8HL	10​	1​
TW8 0EX	WD25 8HL	25​	1​
NW9 0EW	WD25 8HL	10​	1​
WD25 8HL	WD3 8XD	5​	1​

My initial approach without gave all the potential paths without cycles, and you would pick the longest path a driver could do. This way they complete their 8 trips (deliver 8 cars) and no dead ends.
The problem in that approach is that those paths contain those single vehicle edges and each time you complete that edge it reduces the number of available paths. This ends up with "islands" of nodes with a high amount of vehicles to deliver and no paths left to get there.

My new approach I am considering is to try (if I do not give up)
1. Start with the Location with the highest amount to deliver to another location. If there is a tie pick the closest first.
2. Deliver the vehicle to that location (update the values such as incrementing the delivered count / decrementing the to delivered)
3. continue with step 1.
4. If you dead end early roll back a node and proceed to step one
5. continue rolling back until you can complete an 8 trip path (or kick out early)
6. once a location is complete that trip / edge is removed from the search.
7. Now I think this whole thing cycles through multiple times. You keep cycling through all starting nodes keeping only 8 trip solutions until no 8 trip solutions exist for any remaining starting node. Then cycle through taking 7, then 6,....
If I can figure this out, the nice thing about this approach is that as edges complete the looping gets increasing smaller.

 

[Minty]

Hi Maj,

I'm about to go out for the evening but will have a play with this tomorrow, I'll also sort out some more data with real distances and travel times included.

Currently I'm producing this type of output for a list of seventy jobs - the other fields are for presentation purposes, this was the longest chain, but not the one with the least number of starts (fewest dead ends) using a simple loop of from and to postcodes, using all available postcodes as start points, (It's certainly not elegant or clever).

My next stage is to restrict it to 7 or 8 trips and re run, but I've been busy with other projects.

From PC	To PC	Schedule	GroupNo	GroupMax	txtNo
SL2 5DR	HP11 1BH	1	1	1	1 of 1
SL2 5DR	RG4 8UA	1	2	7	1 of 7
RG4 8UA	SL1 5QA	2	2	7	2 of 7
SL1 5QA	HP7 9PN	3	2	7	3 of 7
HP7 9PN	WD25 8HL	4	2	7	4 of 7
WD25 8HL	HP7 9PN	5	2	7	5 of 7
HP7 9PN	SL2 5DR	6	2	7	6 of 7
SL2 5DR	RG4 8UA	7	2	7	7 of 7
SL2 5DR	RG4 8UA	1	3	1	1 of 1
SL2 5DR	RG4 8UA	1	4	1	1 of 1
SL2 5DR	RG4 8UA	1	5	1	1 of 1
SL2 5DR	WD3 8XD	1	6	4	1 of 4
WD3 8XD	AL1 1XB	2	6	4	2 of 4
AL1 1XB	TW2 5NT	3	6	4	3 of 4
TW2 5NT	RG4 8UA	4	6	4	4 of 4
SL2 5DR	TW8 0EX	1	7	26	1 of 26
TW8 0EX	SL2 5DR	2	7	26	2 of 26
SL2 5DR	TW8 0EX	3	7	26	3 of 26
TW8 0EX	WD25 8HL	4	7	26	4 of 26
WD25 8HL	TW8 0EX	5	7	26	5 of 26
TW8 0EX	HP7 9PN	6	7	26	6 of 26
HP7 9PN	SL2 5DR	7	7	26	7 of 26
SL2 5DR	TW8 0EX	8	7	26	8 of 26
TW8 0EX	SL2 5DR	9	7	26	9 of 26
SL2 5DR	TW8 0EX	10	7	26	10 of 26
TW8 0EX	SL2 5DR	11	7	26	11 of 26
SL2 5DR	WD19 4BY	12	7	26	12 of 26
WD19 4BY	SL2 5DR	13	7	26	13 of 26
SL2 5DR	WD3 8XD	14	7	26	14 of 26
WD3 8XD	WD25 8HL	15	7	26	15 of 26
WD25 8HL	TW8 0EX	16	7	26	16 of 26
TW8 0EX	SL2 5DR	17	7	26	17 of 26
SL2 5DR	WD3 8XD	18	7	26	18 of 26
WD3 8XD	SL1 5QA	19	7	26	19 of 26
SL1 5QA	TW8 0EX	20	7	26	20 of 26
TW8 0EX	SL2 5DR	21	7	26	21 of 26
SL2 5DR	WD3 8XD	22	7	26	22 of 26
WD3 8XD	SL1 5QA	23	7	26	23 of 26
SL1 5QA	TW2 5NT	24	7	26	24 of 26
TW2 5NT	WD25 8HL	25	7	26	25 of 26
WD25 8HL	HP7 9PN	26	7	26	26 of 26
HP11 1DD	AL1 1XB	1	8	1	1 of 1
NW9 0EW	WD25 8HL	1	9	4	1 of 4
WD25 8HL	WD3 8XD	2	9	4	2 of 4
WD3 8XD	SL1 5QA	3	9	4	3 of 4
SL1 5QA	SL2 5DR	4	9	4	4 of 4
WD3 8XD	TW8 0EX	1	10	2	1 of 2
TW8 0EX	SL2 5DR	2	10	2	2 of 2
WD3 8XD	WD19 4BY	1	11	1	1 of 1
WD3 8XD	WD19 4BY	1	12	1	1 of 1
HP11 1DD	SL2 5DR	1	13	1	1 of 1
HP11 1DD	SL2 5DR	1	14	1	1 of 1
HP11 1DD	SL2 5DR	1	15	1	1 of 1
HP11 1DD	SL2 5DR	1	16	1	1 of 1
HP11 1DD	SL2 5DR	1	17	1	1 of 1
HP11 1DD	SL2 5DR	1	18	1	1 of 1
HA4 0LN	SL2 5DR	1	19	1	1 of 1
HA4 0LN	SL2 5DR	1	20	1	1 of 1
HA4 0LN	SL2 5DR	1	21	1	1 of 1
WD25 8HL	SL2 5DR	1	22	1	1 of 1
WD25 8HL	SL2 5DR	1	23	1	1 of 1
WD25 8HL	SL2 5DR	1	24	1	1 of 1
WD25 8HL	SL2 5DR	1	25	1	1 of 1
WD25 8HL	SL2 5DR	1	26	1	1 of 1
WD3 8XD	SL2 5DR	1	27	1	1 of 1
SL1 5QA	SL2 5DR	1	28	1	1 of 1
SL1 5QA	SL2 5DR	1	29	1	1 of 1
HA4 0LN	HP7 9PN	1	30	1	1 of 1
WD3 8XD	WD25 8HL	1	31	1	1 of 1
HP11 1DD	AL1 1XB	1	32	1	1 of 1

		​	​	​

 

[MajP]

I'll also sort out some more data with real distances and travel times included.

Thanks. If I can see a real set and a real final shipping plan, then I can see if I can automate that. Then see if it can be improved.

Currently I'm producing this type of output for a list of seventy jobs

I do not understand how to read this. Can you see where a driver starts and all the trips they make along a "chain"? How do you see the dead ends?

At the worst case maybe a good GUI that allows to quickly build a chain, roll back if you dead end, and add a completed path to the overall shipping plan. You will see the requirements update as you assign drivers to trips like I show on the right subform.
1. Pick a driver
2. Click to assign a "trip" by picking a start and end
3. Show where you can go next and and what is availabe to move
This would instantly show what was assigned and what is left
4. show the path as it is built
5. Let you quickly un assign a trip to "roll back"
6. once you complete a chain then assign to overall shipping plan

This may be one of those problems where the brain can pick a good solution if given good visibility of the data, while coding that same decision making is really complex.

 

[jdraw]

For what it is worth, I asked a question of BingChat the other day. What is the distance between postal codes and gave it 2 from Minty's post. It did it immediately. So I then said what is the distance between these unique From and To postal codes. I am attaching the list. I do recall from other postal code work that postal codes represent areas, so distances between are working with some "representative point"/ centroid of the postal code area. Locations in some postal codes could be quite different than the centroid, so distance at best is an approximation.
Anyway, a little use of AI/Bingchat to assist. Hope it is helpful.

I'm impressed with MajP's efforts on this.
Good luck.

 

[Minty]

This may be one of those problems where the brain can pick a good solution if given good visibility of the data, while coding that same decision making is really complex.

I think this is where I will be heading at this stage, provide a lot of visual and data aids as a starting position, for the human to finish it off by knowing and understanding things that are external to the known data.

I've been too busy to get you sample data so far today, but will come back to it later.

 

[MajP]

I've been too busy to get you sample data so far today, but will come back to it later

No problem. The distance thing is really just a tie breaker or secondary consideration and not really necessary. I do not think it really add complexity to the problem. Finding any candidate chains that drive to a good solution it would not be much harder to pick the shortest good candidate chain.
I will continue to play with this until I feel defeated or have no more insight. I think this is a very challenging graph theory problem, so I may try to find a place to post this for some real experts to give insight.

 

[MajP]

@Minty, I figured out a very useable interface that provides more utility then I thought. This is pretty slick if I say so myself.
Most importantly it allows building a path ("chain") very quickly, provides a lot of insight on status and where to go next, and allows you to "roll back" a path to explore other routes.

I use the term "Trip" to mean moving a car from one PO to another
I use the term "Path" to be a linked group of trips

1. Here you can start creating a path by picking a driver. As you assign trips to the path you see the number of trips, total distance, and the path
You can remove a path from the shipping plan
2 This shows the Trips for the path selected in the Paths subform. Start, End, Trip Distance, number of cars shipped on that trip, number of piggybacks, Total cars required to ship, and remaining.
3. This button allows you to remove the last trip. This allows you to "rollback" if you hit a dead end and follow a different route.
4. Here you select a trip to add to the path. They are sorted by the trips with the most vehicles to ship and then by distance. You want to select in order, but you may hit a dead end. Most importantly this list only shows trips starting from the last ending location.
5. This is the overall status. The datasheet view is nice since you can quickly sort and filter by number of vehicles remaining, start vertex, end vertex, This then allows you to project forward and make informed choices.

Green (0 vehicles left to ship)
Yellow (1 vehicle left to ship)
Red or none (more than one vehicle left to ship)

Here you can see the Trips for the selected path, and you can only select the next trip starting at WD3 8XD which is where that path last ended.

 

[Minty]

@MajP , that's a really slick way of displaying and interacting with the data, it makes trialling the options very quick and seems intuitive, at least to my initial quick play with it.

I'll should have time today to get you some of the actual routings they have used.

 

[MajP]

I will add a couple of more features that will make this even more intuitive.
Since there is a little room I will put a tab control where the right subform with the overall shipping status is located. On the second tab will have two subforms. The first is list of locations that show the total remaining number coming into the location and the total remaining number going out. Ones with more coming in then going out identify a potential where you want to piggyback. I assume a piggyback is better then a dead end. I assume a driver can do eight trips either driving or piggybacking.
Next to the bottom subform i will put another subform. This way the current record on the bottom subform will show next to it if a piggyback is available (someone already drove that trip). This will allow you to assign a person a trip that has no cars to ship. Show you if a piggyback exists, and then automatically assign the current driver a piggyback with another driver.
I played with this and if gives you a good view where to assign a piggyback and how to assign it.

 

[Minty]

I was going to ask about the piggyback status, and how it worked.
Sorry I've been very tied up with other work which is stopping me from digging into this properly.