Optimising Routes

[MajP]

i was going to ask about the piggyback status, and how it worked.

You can pick a trip that has 0 vehicles to ship. You will see if another driver has previously driven that trip. Then it will assign the current driver as a piggyback and not increment the number of cars shipped on that trip.

 

[MajP]

So I added another subform that gives some more awareness. This shows the total number of vehicles coming into and leaving a location.
If the number coming into the location is greater than the number going out then you are probably going to need to set up a piggyback out of there. If there is less coming in then going out then you have to likely piggyback in.

It is set up now if you select trip to add to the path and another driver previously drove the bath you will see they are available piggybacks.

Here I select the trip SL15QA-->SL25DR and see that abe and bill already traveled this trip. So that means a piggyback is available. Since there are no remaining cars to ship it will automatically assign a piggyback.

After assigning that trip to the route you can see that it created a piggyback assigning the current driver to Abe.
I need to add a check to see if the number of piggy backs does not assign the available sears (3 passengers), but that is doable with a little more code. I assign the first driver to piggy back with, but I should provide a means to select which driver if there is more than one.

 

[MajP]

Added another tab for SA of the complete shipping plan.
On the "paths" subform for each path I show the amount of trips in the path, total path distance, number of cars delivered in the path, and number of piggybacks.

In the summary tab for the entire plan I show number of paths, total cars shipped total piggybacks, and total trips.
If a path is less than 8 trips that is a "dead end" path.
Lost trips is the number of trips less than 8. In the image one path only had 5 trips so the plan has 3 lost trips. This accounts for the fact that the shorter the path the worse it is. A path that dead ends at 5 is worse than one that dead ends at 7 trips.
Missed deliveries includes piggybacks. A path should deliver 8 cars the missed deliveries is the number of cars delivered. So there are 4 missed deliveries. A piggyback may not be as bad as a dead end. My assumption is that a driver gets eight trips a day regardless if they are driving or piggybacking.
Unfortunately as I added these extra things, I did not do it smartly. This has become very slow, so will have to refactor. The bigger issue is that I probably should have designed this so you can develop many plans. You can only build one plan now. Obviously that would add quite a bit of complexity. However, I still think this is a good proof of concept.

 

[Minty]

@MajP Thank you I'll have a look shortly, but that sounds like a very interesting update.
I'm currently suffering from a case of "Man-flu" (A nasty cold) so my ability to concentrate on complicated things is rather limited by brain fog at the moment.

 

[Minty]

I thought I would upload some other sample data. This has real mileages and travel times.

The second table is using my existing find the best number of routes with a maximum of 7 trips in a "chain"
On the second worksheet is that actual schedule the client used for that day, I don't have the details of any piggybacking unfortunately.

I'll upload the data from these to your demo this afternoon, and see how it compares.

 

[MajP]

I'm currently suffering from a case of "Man-flu" (A nasty cold) so my ability to concentrate on complicated things is rather limited by brain fog at the moment.

I do not know if people understand the seriousness of the man-flu, but here is a PSA:

I am coming off of another round of man-COVID which is equally as severe, so I empathize.

I keep playing with this in my free time. Added a few more bells and whistles for demonstration. See added buttons at top.

I added a Settings form. Here you can set the desired length of Trips in a path and start time.

I added an export feature for Summary Shipping Plan. This will show how "good" of a plan with number of dead ends (paths less than max desired trips), along with piggybacks. I assume a piggyback is not as bad as dead end, but not sure. If a driver takes a 6 trip path resulting in a dead end (where max is 7) they deliver 6 cars. If they take a 7 trip path with a piggyback they still only deliver 6 cars but it allows them to continue on without using public transportation or another means.

I added an export feature for the Detailed Shipping plan which mimics your spreadsheet with added detail.

Things to do:

Putting my "Operations" hat on, I am guessing at how you would use this. I think if I was going to do this I add another table because there is going to be requirements to create multiple shipping plans for different days with different shipping requirement and potentially different to-from locations.

tblShippingPlan
-planID
-planName
-ShippingDate

Now you can store plans for multiple dates.

I call them edges or trips but I would then modify my current table that has all the edges/trips with start location, end location, distance and times. In this table I would remove the shipping requirement (number of cars). This is now just the reference data to first build the shipping requirements for a plan.

I would then modify my current edges table to be the tblShipingRequirements. Now you would select
tblShippingRequirements
-ShippingRequirementID
-PlanID_FK
-EdgeID_FK
-RequiredToShip

So with this design you first have a form to select the Trips/edges (jobs) for a plan and then assign the required number to ship. This would allow you to build different plans. I assume some days you do not ship from every location.

With the piggybacking you now have the visibility to see who else is going on that same "trip/job" and when they arrive at that location (sort of). This will identify roughly how long to wait for the arriving driver or how long a piggyback driver would have to wait for the passenger. Then I realized there is more to this that could be added. I currently assign the current driver to a piggyback driver, but not yet save in the piggyback driver's record who they pick up. This probably would need to be a child table so that a driver can pickup more than one other driver. Also need to save information on how long the piggyback driver needs to wait for the pickup if they arrive prior to the driver they need to pickup.

Again I assume that drivers start at potentially different times. To synch the piggybacks sometimes a driver would have to wait for ride or passenger if arriving at that location from different trips or time. I realized that this gets complicated because I show running time as just the amount of time for travel from node to node, but to really try to synchronize this it would be Start Time + running trip time + delay for piggybacks + length of time at each drop off. I think this is possible based on the structure just requires work.

With some practice if you use the two subforms on the right it provides good visibility to when a piggyback works. You can see if you piggyback into a node what other paths you can then jump to.

You can see from my plan so far
I did 10 paths of 7 trips with 7 cars deliverd
I did 1 path with 7 trips and 1 PBs and 6 cars delivered
I did 1 path with 7 trips and 2 PBs and 5 cars delivered

On the operational side I am not sure how you handle this, but I think you will often end up like this. The above shows what is left to come into or go out of a location.
The problem is what you do with the remaining. You have some nodes with a lot of cars to ship, but they go to dead ends. Or you have a node with a lot coming in and little or none going out. In my mind maybe you have a company van to do this cleanup. Drop a group of 7 drivers off at several nodes that all go to WD258HL. Pick those 7 up and take them to AL1XB. This alone wipes out more than half the remaining to ship.
Do not know if that is an option.
Or the other option is they get to a dead end and bus/public transportation over to the next delivery point. Adding a bus Trip is doable, with some modification of the code. Currently you can only select another node that the current node connects to. A bus edge could be added that connects any two nodes.

 

[Minty]

Covid - not great - hoping you recover quickly. I've now got rid of the cold and am left with an annoying cough

That latest version looks interesting, and I will have a play around later.

Operationally, each day can have a massive variation in number of vehicles being moved, locations and therefore routes.
A really busy day is >100 movements, a quiet one can be as few as 15 or 20.

A piggyback is perfectly acceptable, as is ideally finishing as near to the starting point as possible, but that's outside the current scope of looking at this.

The initial goal is to simply speed up the initial working out when there are a lot of jobs, then maybe to refine it to generate a complete plan, which they will probably adapt based on the available drivers and where they can start from.

 

[MajP]

A piggyback is perfectly acceptable, as is ideally finishing as near to the starting point as possible, but that's outside the current scope of looking at this.

So that could be a possible feature. You would still have the ability to create the path manually, but I have the code to "find" and suggest paths. You could add a button to select start location and end location and have it propose a path if it exists that can get there in the required amount of trips (7). Then you can choose to accept the path. I have now a lot of code for searching based on my previous shortest path and breadth first search.
Another useable search would be to find dead end nodes (nodes with no vehicles leaving, but ones arriving) and have code to search for a path that ends at that node by working backwards. This way the application could suggest paths of 7 trips that end at a dead end node.

The initial goal is to simply speed up the initial working out when there are a lot of jobs, then maybe to refine it to generate a complete plan, which they will probably adapt based on the available drivers and where they can start from.

That is probably another thing I need to modify. I create a new path by first assigning a driver. That is probably not how you do buisness. You may or may not know who you are assigning until after creating the plan. Then when you are all done you assign the drivers. So I probably need to modify where you can assign a driver or not to initially create the path.
However, I think what is here should speed up creating the initial plan.

 

[MajP]

I keep playing with this out of intellectual curiosity and in and IMO this works extremely well for getting very good solutions, quickly and efficiently. It is an interesting problem in trying to design a UI that can present this information in a way that you can understand how this different trips connect and what remains to move from different locations.

I believe this approach is better than a potential optimization, because I am guessing in real life you will have so many changing requirements and one off requirements
Ex (1 driver need to be done by noon, 3 drivers have to start at point A, driver 7 need to end at B, There is traffic between C and D at 10-12 so leave first or last, etc.) This gives you the ability to build specific Paths to meet those requirements. However, I do think I can build some more features to help recommend the next path.

Because you are rolling up information and self referencing that amount of queries got a lot quick. Data needs to roll up at the trip level, path level, and plan level.

Note: I use this terminology in the below discussion

Job: Requirement to move car from one location to another

Trip: Movement of a driver from one location to another either completing a Job or riding as a passenger (piggy backing)

Path (group): The assignment of Trips to a driver (A->B->C->

Real Dead End: A location that has vehicles arriving, but none departing
Created Dead End: A location that has vehicles arriving, but no vehicles remaining. This presents an opportunity to piggyback because another driver is moving on this trip.

Driver Wait for Passenger: A driver can arrive at a location prior to a another driver who will become the piggy back passenger. The driver needs to wait at that location until the "passenger" arrives

Passenger wait for Driver: A passenger can arrive at a location prior to a another driver who will become the piggy back driver. The passenger needs to wait at that location until the
future driver arrives
(note:You may think why not always make the first arriving driver the Piggyback driver and the latter the passenger. This would require recalculating previous assignments and might be more confusing.)

Shipping Plan: The daily assignment of trips to paths to deliver all vehicles. (Currently you can only build 1 plan at a time)

The trick is to provide as much visibility in picking the correct trips in the correct order and provide an interface to do this quickly. As I kept trying to provide myself visibility, I just kep adding more and more.

I believe to formulate a good plan you want to pick trips as follows. The tool lets you see this.
1. Start with a location that has few vehcles being shipped in and a lot of vehicles being shipped out. Even better is a lot of vehicles going to many locations. There will be locations with no ways to get to it so obviously start there. If that same location has vehicles going to many locations then you have many options for paths to follow
2. As you add trips most likely want trips with a lots of vehicles to deliver, but you do not want to go to a place you cannot get out of. The tool provides this visibilty
3. Finally, you ideally want to end your path at those locations that are dead ends. You want to complete those jobs, but not early.

Piggybacking
My assumption is that piggybacking is better than not, because a driver can continue on a path without taking public transportation somewhere.


Max Trips / time / distance
You mentioned that a driver can do eight trips a day.
1. Is that a desire because drivers get paid for deliveries or is that a limitation on time or miles on the road? There is visibility either way
2. If the driver takes a piggyback does that count as a trip? If not this makes getting a good solution easier. A driver could take 10 trips and deliver eight cars opening up more options
If the drivers are actually limited by miles or time the application show total miles on a path and cumulative time (this includes waiting for a piggyback).

Dead Ends
1. Say a driver completed four deliveries (a-b-c-d-e) and arrives at a dead end, what do they do? Do they get on a bus to another location and complete 4 more (take bus to k, k-l-m-n-o)?
The app is set up so you could create a second path for that driver, but currently there is not means to track the time between the first and second path based on bus travel.
I think the data structure could support a "Bus" node assignment, but would require some work. (a-b-c-d-e-busE-busK-l-m-n-o).

This thing has a lot of moving parts and had to provide a user manual, but it has a lot of capability. If you can actually use it great, if not it has been an interesting puzzle to try to solve.

One thing I have not figured out is leveling the wait times. The thought is to really do this you would like to know that if you get to a location where there are a deficit of leaving vehicles you can plan who is the piggyback driver and when they get to the location and when the passenger gets to the location. Somebody will likely have to wait.

I do correctly add the wait times when a piggyback and when there are no dependancies. However imagine this scenario.
Path X driver A
Path Y driver B
Path Z driver C

When Path Y is entered driver B piggybacks with the driver A on a trip. The wait times are calculated. And lets say B waits 10 minutes for A to Arrive.
When path Z is entered assume C get a piggyback from B prior to B getting a piggyback from A. Lets say B has to wait for C 15 minutes. Now the schedules impact and have to be leveled. B no longer waits for A to arrive but instead A has to wait 5 minutes for B to arrive. I have not figured this yet.

 

[MajP]

@Minty,
Now the Coup de Grace.
I finally figured out how to find paths with cycles. Once I started thinking about it, it was a lot easier than I thought. The thing is that you can only cycle so many times (go back to a location in the current path) until you remove all possible vehicles from that location.
If anyone wants to learn how to do a depth first search of a graph with cycles and dynamic decreasing edges, i can explain. I have never seen anyone do this.

Now you can provide a start location, end location, and the number of trips. You can find the following paths.
1. All available paths from start to end of N trips
2. All available paths from start to any end of N trips (select Any Location for end)
3. Longest trip from start
4. Any available path of N trips

It will show you the preferred path (sorted) by best, but you can pick another path.
You can then create a new path in your shipping plan or add the found trips to an existing path.

More importantly I have a button called "Recommended Path". I call this my "draining" algorithm. This solution finds the prefered start, stop, and trips in between.
The logic is you want to always start from a location that has no arrivals (or few arrivals) and end at a location with no departures (or fewest). Then it picks trips in between that have the most vechicles to deliver. My draining algorithm is basically "draining" locations with a lot of vehicles to ship so that you do not create islands.

Although you can click manually "Recommended Path" and then "Create Path from Trips" and build your plan this way, I now have a button to do this all manually.
You can on the main form select "Create Plan". This will create as many possible paths in the plan that are of the default max length.
In this example if you delete the current plan and then select Create Plan it will create a plan with 10 Paths of 8 trips. This delivers 80 of the 105 vehicles with no deadends.

Now you have to do the rest manually since there are no more trips of 8 possible without assigning piggybacks.
1. Pick Recommend New Path with number of trips = 7
It will not find a viable path with more than 5 trips
2. Pick this path
3. Assign piggybacks
now use the start to end search to go from the piggyback location to find a path to add to the existing path.
This may take some training, but making trips of a certain length with viable piggybacks is very easy.

I really do not think you can build a more useable application to do this.

 

[jdraw]

MajP,

Very impressive!