Search code examples
mathematical-optimizationor-toolsvehicle-routingoperations-research

How to bundle pairs of trips?

I have a database of optional real-time trip demands. Each with a load that can to be delivered from a departure point to a destination:

ID,EndDateEnd,EndDateStart,StartDateEnd,StartDateStart,DepX,DepY,ArrX,ArrY
1,2021-03-04,2021-03-03,2021-03-02,2021-03-01,2.83689,47.3324,-0.5854,44.83814
2,2021-03-04,2021-03-03,2021-03-02,2021-03-01,2.44774,47.56044,0.13888,49.49015
3,2021-03-10,2021-03-09,2021-03-08,2021-03-07,2.76755,47.97472,0.65567,48.78064
...

It is a list of load offers that companies need delivered at a certain location and time.

My goal is to bundle pairs of loads that increase my truck's paid miles. I normally have a set destination and origin. Let's say I'm going from NYC to CHICAGO. Then I search on the trip database for loads that need to be delivered along that route. Imagine I find one with a pickup in Pittsburg and delivery in Cleveland. Then my paid miles would be the driving distance from Pittsburg to Cleveland. But I'm not getting paid for getting from NYC to Pittsburg or from Cleveland to Chicago. A picture is better for explaining:

enter image description here

In blue you can see the paid miles and red the not paid miles. If I could find another load from NYC to Pittsburgh it would be great or Cleveland-Chicago as well.

Now the question is how can I algorithmically find pairs of loads that go well together given a route? I know my part and end of the trip. I just need to go through the list of trips to find the best ones for me.

-Going well together is a loose definition. Generally speaking increasing the % of paid miles is the goal.

One solution I have researched:

You could define that two loads "go well together" if the miles driven from only one truck doing both loads is lower than two trucks doing each one of the loads.

That is the intuition behind the Clark and Wright Savings Method.

enter image description here

Being d your favourite distance function. In our example, start is NYC and END is Chicago. The pickups and deliveries are from the candidate pairs of bundles. If the savings are high then it is a good bundle.

This is a type of vehicle routing problem that is sometimes called pick up and delivery with time windows(PDPTW) I'm trying to solve a smaller part of them problem. Just finding useful pairs of trips.

Are there any other solutions out there? Scaleable approaches to bundling?

Relevant Research Papers:

Cross post: https://or.stackexchange.com/questions/8159/how-to-bundle-pairs-of-trips

Solution

  • There is a pdptw example in the routing library:

    Simple Pickup and Delivery problem in C++