4
$\begingroup$

I have a database of real-time optional trip demands. Each with a load that needs 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 start 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:

$\endgroup$
6
  • 1
    $\begingroup$ Can you pick up a load before having delivered the one which is already in the truck? If yes, does the truck have a capacity constraint? $\endgroup$
    – fontanf
    Mar 29, 2022 at 14:12
  • $\begingroup$ @fontanf no, max 1 load. $\endgroup$
    – italo
    Mar 29, 2022 at 17:24
  • $\begingroup$ More questions: Are you planning just one route or multiple routes (implying that loads assigned to the first route are not available for the second route)? Do all loads have to be delivered, or can you ignore loads that don't fit nicely into a route? What is the significance of the dates in your data? If loads have to leave within the start date range and have to arrive within the end date range, are you assuming that all routes require a single travel day, regardless of how many pickups and deliveries (and the distance)? $\endgroup$
    – prubin
    Mar 29, 2022 at 23:28
  • $\begingroup$ Do you have the order of magnitudes of the problem? Total number of pairs and number of pairs in a trip mainly $\endgroup$
    – fontanf
    Mar 30, 2022 at 7:18
  • $\begingroup$ @prubin, -Multiple routes are planned everyday. The loads can be used on two routes because we don't "assign" the loads. We just show the loads available given the particular route. -You can ignore routes. -You are right, the dates limit the pickup and delivery. There is no assumption. The travel time could be 3 hours. Also, we are only bundling 2 pickups and deliveries. $\endgroup$
    – italo
    Mar 30, 2022 at 9:34

2 Answers 2

3
$\begingroup$

If you care only about pairing and not routing, you have a maximum-weight matching problem. For each compatible pair $\{i,j\}$ of loads, let binary decision variable $x_{ij}$ indicate whether these loads will be paired, and let $s_{ij}$ be the corresponding savings. The problem is to maximize $\sum_{i,j} s_{ij} x_{ij}$ subject to $$\sum_{i,j:\ k \in \{i,j\}} x_{ij} \le 1 \quad \text{for all loads $k$}$$

$\endgroup$
2
$\begingroup$

Since delivery must be done directly after pick up, it looks more like an Asymmetric Orienteering problem to me, where a visit corresponds to a pick up and its delivery. The subtlety in this case compared to the traditional Orienteering problem is that visiting a location takes some time.

Input:

  • $n$ locations, an $n \times n$ matrix containing the distances between each pair of locations (not symmetric); for each location $j = 1..n$, a profit $p_j$ and a visiting time $t_j$
  • a time limit $t_\text{max}$

Problem:

  • Find a path starting at location $1$ and ending at location $n$ such that:
    • each location is visited at most once
    • the arrival at location $n$ is before $t_\text{max}$

Objective:

  • Maximize the total profit of the visited locations

I can propose you an alternative greedy approach that builds a solution following a "forward" scheme (i.e. adding the visits in the order they are performed), using the profit / time to asses the quality of the partial solutions:

solution <- []
current_time <- 0
current_profit <- 0
current_location <- 1
while True
    best_location <- -1
    best_value <- -1
    for each new_location in the remaining locations
        new_time <- current_time + distance(current_location, new_location) + visit_time(new_location)
        # Check time limit constraint.
        if new_time + distance(new_location, n) > time_limit
            continue
        new_profit <- current_profit + profit(new_location)
        new_value <- new_profit / new_time
        if best_location == -1 or best_value < new_value:
            best_location <- new_location
            best_value <- new_value
    # If no more visit can be added, then stop.
    if best_location == -1:
        break
    # Update current solution.
    solution.append(best_location)
    current_time <- current_time + distance(current_location, best_location) + visit_time(new_location)
    current_profit <- current_profit + profit(best_location)
    current_location <- best_location
return solution

It's what looks the most natural to me. With more time for the development and the resolution, I would consider extending it into a tree search algorithm

$\endgroup$
2
  • $\begingroup$ hey @fontanf what is the difference between a location and the pickup and delivery points. The profit is only added at the delivery point or what is the logic? $\endgroup$
    – italo
    Apr 1, 2022 at 16:43
  • 1
    $\begingroup$ @italo location and pickup and delivery points are the same. It's just that in your case a "pickup and delivery" is closer to what is usually called a "location" rather than what is usually called a "pickup and delivery". Therefore, if you look for algorithms for "pickup and delivery" problems, you might not find many relevant elements $\endgroup$
    – fontanf
    Apr 1, 2022 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.