The Situation
Deliveries were at least once a week from each PDC to the 640 depots. So each depot had at least three deliveries per week, and thus there were around 1900 deliveries in total, every week. Apart from high sales weeks and holidays, each week followed the same delivery schedule. However, it was a unique transport planning problem every day due to varying volume demand.
Besides the PDCs, there are four locations around the UK called ‘outbases’ and were used to reposition loads from the three PDCs before delivery. The reason for having ‘outbases’ was to maximise the use of resources. For example, many places in the UK take a driver over his maximum drive time for a shift, which limited the distance he could travel and resulted in a night out. During that night out, the vehicle was unavailable for work and parked away from the base. Using an ‘outbase’ system allowed vehicles to be planned in a relay, with loads transferred throughout the network within a 12-hour window. Vehicles returned to base within driving limits to be re-manned and used for another shift.
A vehicle consists of a tractor and a trailer that can be unhitched where necessary.
Our Approach
This study aimed to apply Opturion’s state-of-the-art optimisation and scheduling technologies to provide optimal solutions for Howdens’ transport of products. A test case was studied to illustrate how effectively the problem could be solved.
Howden’s supplied Opturion with data on delivery orders. The data included information on the location of PDCs and ‘outbases’, delivery locations (depots), weight and volume of each order, and vehicle information.
There were many loads, each of which consisted of several drops. Therefore, we decided that the load plan would be followed, including the order of the drops. This approach strongly restricted daytime deliveries optimising potential, but it still allowed a roaming fleet (i.e. vehicles picking up from multiple depots) and an optimised night plan.
Stage 1: Re-Allocating Jobs
We re-allocated jobs from each of the PDCs to other PDCs and ‘outbases’ in the first step. This was done based on the geographical spread of the jobs and presumably remained reasonably static. However, the reallocation implied some nighttime repositioning work.
Stage 2: Daytime Deliveries
As a second step, we solved the daytime problem, which was modelled as a combined tractor-and-trailer optimisation, to make use of our unique tractor-and-trailer optimiser. The tractor-and-trailer optimiser supported that trailers may have differing capacities and supported pre-loading with hitch and unhitch operations taking less time than loading the trailer.
For jobs that could realistically be served (during the day) from multiple PDCs or ‘outbases’, we let the optimiser make the reallocation decision dynamically (i.e. perform part of Stage 1). However, we did not recommend this for all of the jobs, as it would unnecessarily complicate the optimisation task.
Howdens applied a trailer capacity limit (m3) that depended on the number of drops in the load. This was not a default feature of our optimiser, but the technology easily supported arbitrary constraints on what constituted a valid load. For this case, however, we used the limit corresponding to the case of one drop.
Stage 3: Night-time Deliveries
As a final step, we solved the nighttime problem. Here, we repositioned fully loaded trailers from each of the PDCs to the other PDCs and ‘outbases’. The Stage 2 optimisation implied the number of trailers that were moved. In effect, this was a simple pickup and delivery problem instead of a tractor-and-trailer optimisation as complete trailers were delivered. We made use of trailer swap locations in several cases where the travel would otherwise have exceeded the 13 hour work time limit or the 9 hour driving time limit. In such cases, the job consisted of several alternate legs, i.e. go from A to B directly or go from A to C and then from C to B. These were also the only times where tractors from the ‘outbases’ were used at night. In a real-life scenario, we would have had to reposition trailers resulting from the previous day’s work.
The Results
Day Shifts
All loads were delivered within the constraints, but an overnight stay was required for two loads.
Night Shifts
All repositioning jobs were carried out within the capacity. The results were calculated by the optimiser within 5 minutes. If the two-way journeys between the three PDC and ‘outbases’ exceeded the maximum driving hours, they were broken into multiple segments using swap locations.
In the instance where there were gaps between the first and second parts of the journey, i.e. trailers get to a location earlier than vehicles scheduled for delivering, the trailers needed to wait to be moved. In this case, the waiting time was no more than 25 minutes for each trailer. On the other hand, waiting and trailer storage were not needed for journeys with no gaps between the first and second parts, as the vehicle from the first part of the journey was swapped on arrival with the vehicle used for the next part.
To further improve the productivity of vehicles, the requirement that each trailer should return to its start location after the deliveries was relaxed. This relaxation gave tractors a chance to roam around DC’s, i.e. a tractor from one DC could carry out jobs for other DCs. All other parameters were the same. Therefore, roaming increased the utilisation of vehicles. In the routing with roaming, we compared the utilisation of roaming vehicles with non-roaming vehicles. The utilisation was measured by travel distance, work time and driving time.
When distances became too large to deliver directly from the depot (DC) to customers, staging deliveries beforehand was necessary. In this study, we showed that we were able to solve dynamic staging problems, including the option of having multiple changeover points, with or without the capacity to store trailers. We also showed that there could be substantial benefits in having a fleet roam between DCs, which showed a potential cost reduction of up to 10%.
