A classic vehicle routing model checks every tour on its own. Each tour has its own capacity, its own time windows and its own driver, and the tours only meet in the total cost. That is what makes the problem tractable. It is also why so many optimized plans fall apart in the yard.
Two things in freight break that independence. A dock can hold one truck at a time, whichever tour it belongs to. An empty container taken by one tour isn't there for the next one. We looked at how operations research handles both, and built the ideas into the planner that runs Transportial's optimizer and /vrp/solve.
Docks: Bombelli and Fazi (2022)
A. Bombelli and S. Fazi studied trucks that collect air cargo from forwarders and deliver it to ground handlers at an airport. A ground handler reserves only one or two docks for them. Their paper models it as a pickup and delivery problem with time windows in which a dock can't serve more trucks than it has.
Their heuristic is an adaptive large neighborhood search. Each route stays feasible on its own, but the plan as a whole may overbook a dock at a penalty. After every insertion a resolver walks through the dock conflicts in time order. For each one it delays the truck that can be shifted least, which is free if that truck has slack.
Their findings are worth knowing for anyone who plans to a dock:
- Without coordination, trucks queued for up to about three hours, and some plans became infeasible.
- Coordinating the docks cut travel time by 2 to 19%.
- A second dock mattered mostly for feasibility: both docks were in use at the same time less than 10% of the time.
What we built
Our planner keeps a timeline per place with a limit: a dock, ramp, berth or rail siding, the same for every mode. The timeline holds the stays of every tour in the plan. It also holds what is taken from outside the plan: other trips already at that place and dock timeslots that are already booked.
When the planner times a tour, it asks the timeline at each limited stop. Service starts as soon as a dock is free for the whole service, if the time windows still allow it. The wait counts as real waiting, in the driver's day and in the tour's time and cost. Each limited stop costs one lookup, so testing a candidate stays cheap, and a plan without dock limits runs exactly as before.
Here we deliberately departed from the paper. Our search also juggles driver clocks, trailers, compartments and equipment stock, and an overbooked dock would make every one of those times uncertain. So we keep every plan the search holds dock-feasible:
- Making room. When a candidate tour can't wait in time, the tours in its way are timed after it if they still fit. That is the paper's "the truck that can shift gives way". The candidate pays for their extra time, and if no shift works, the insertion is refused.
- The resolver. After every accepted move, a tour that waits gets the dock first when the tour holding it could wait at less cost. Typically that is a shift within slack, and the swap is only kept when it shortens the two tours' combined time.
- Fixed reservations. Existing trips and booked timeslots never move.
If you'd rather allow overbooking, set the dock_capacity rule to warn. A tour may then overbook at a cost per minute, and it is reported, as in the paper.
Empty containers: Fazi, Choudhary and Dong (2023)
S. Fazi, S.K. Choudhary and J.X. Dong studied container carriers working from an inland terminal. A truck makes several trips a day, one container at a time.
- Where empties come from. An export needs an empty: from the terminal's limited stock, from an import that was just unloaded (a street-turn), or from a distant depot.
- The hard constraint. The terminal's stock of empties may never go below zero, at any moment. That ties the trips of different trucks together.
- Their solution. They solve it exactly, with branch-and-price. The stock constraint is only checked at "critical times": the moments a trip takes an empty out, because stock can only run short when a unit is taken. A detour to the depot is priced into the arc instead of becoming an extra stop.
On real cases near Tilburg and 's-Hertogenbosch, their plans were 25 to 43% cheaper than the ones the planners had made, with fewer trips. They also tested what happens when conditions are tighter. Fewer street-turn opportunities raised costs by 2 to 12% in the real cases, and starting the day without empties in stock raised them by up to 27%.
What we built
A shipment can now say it needs a unit at its pickup, it frees one after its delivery, or both. A unit can be an empty container, a swap body or a pool trailer.
When the planner builds a tour, it looks for a source for each needed unit in this order:
- A unit freed earlier on the same tour, if both shipments allow a street-turn and the truck can carry it in between.
- The stock or depot that adds the least distance, fetched on the way to the pickup.
A freed unit that isn't reused goes back to a stock on the way after the delivery. Like the paper's depot arcs, these visits are priced into the leg as time, distance and cost, rather than becoming stops.
Across tours, one book holds every tracked stock: its start, known arrivals and departures, and every tour's takes and returns. Following the paper, it only checks a stock when a unit is taken. A take that would drive a stock below zero moves on to its next source, and if none is left, the equipment_stock rule decides. Trips that already exist count with their open takes and returns.
We are not running branch-and-price. A large neighborhood search tears plans apart and rebuilds them, and removing a tour can leave another tour short of the empty it was counting on. So the search charges each unit short like a shipment left out, and the final pass re-sources or removes whatever is still short. The plan you get never sends two trucks for the last empty in the yard.
Where the two meet
The interesting part is where the two mechanisms touch. When the planner retimes a tour for a dock, the moment that tour takes or returns a container moves with it. If a return slips past another tour's take, a stock that looked fine can suddenly run short. In our planner a retimed tour carries its equipment plan with it, so the stock book always reflects the tour's real times.
This is the point of putting everything in one search. In separate tools, nobody would notice. The dock screen would push a truck back, the empties desk would be right about the morning's stock, and the plan would still fail.
What we left out
- Separate loading and unloading docks, and docks reserved for certain vehicle types. All operational docks of a site count together.
- Chassis pools. The container's source is planned; a pool of chassis shared between trucks is not.
- Equivalent container types (ISO size-type groups) and yard capacity. Types match exactly, and returns are never refused for a full yard.
- Equipment stock and scheduled rail or barge services in one request. For now, plan the road legs as shipments.
Read the papers
- A. Bombelli and S. Fazi (2022). The ground handler dock capacitated pickup and delivery problem with time windows: a collaborative framework for air cargo operations. Transportation Research Part E 159, 102603.
- S. Fazi, S.K. Choudhary and J.X. Dong (2023). The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research 310(1), 343–359.
We built on the published work. The authors weren't involved, and any shortcomings of our adaptation are ours. For what else the planner decides in the same search, read One Search, the Whole Freight Plan. For the fields to use, see the multi-modal VRP guide.
