Competition and Cooperation in Pickup and Multiple Delivery Problems

Abstract

Logistics is a highly competitive industry; large hauliers use their size to benefit from economies of scale while small logistics companies are often well placed to service local clients. To obtain economies of scale, small hauliers may seek to cooperate by sharing loads. This paper investigates the potential for cost savings and problems associated with this idea. We study dynamic scheduling of shared loads for real-world truck haulage in the UK and model it as a dynamic pickup and multiple delivery problem (PMDP). In partnership with Transfaction Ltd., we propose realistic cost and revenue functions to investigate how companies of different sizes could cooperate to both reduce their operational costs and to increase profitability in a number of different scenarios.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

With over six thousand hauliers in the UK alone [15], competition is fierce. Hauliers face the orthogonal demands of short notice from customers, an expectation of low-cost service, and environmental sustainability concerns [12, 21, 24]. Because larger carriers can leverage economies of scale to benefit in routing and scheduling, competition is getting ever stronger. If smaller carriers could work together, they could increase scheduling efficiency, save on mileage costs, and improve flexibility. In this paper we quantify the savings possible when carriers outsource some of their customer consignments to other carriers, working either independently or as a group.

As a real-world problem, there are constraints that must be satisfied, such as vehicle capacity, soft time windows and driver working hour rules. The problem is defined in terms of consignments which include a single pickup location and one or more delivery locations. Consignments vary in size, and may be able to share one delivery vehicle, to save cost. A key constraint is that each vehicle must be unloaded in the reverse order to the loading order: deliveries from one vehicle are constrained to a last-in, first-out (LIFO) order. Concretely, consignment A may be interrupted by another if all of the second consignment’s deliveries are serviced before continuing with consignment A’s deliveries. We call this a pickup and multiple delivery problem (PMDP). This paper investigates the cost savings which are possible if carriers distributed across a country share consignments.

2 Related Work

Research on PDPs usually concentrates on static models of small scale problems such as servicing taxi requests, or ride sharing schemes [29] – dial-a-ride problems (DARPs). [13] present a widely accepted mathematical formulation for the generic PDP, which they refer to as the vehicle routing problem with pickup and delivery and time windows.

Variations of the PDP handle constraints on the number of vehicles used, time windows on requests, capacities and number of depots. However, most of the existing research is on static problems, in which all requests are known in advance [4]. Exact solutions to static PDPs favour branch-and-cut-and-price algorithms using column generation techniques, for example, [16] uses this approach to solve a multi-depot PDP for problems with up to 55 requests. No indication is given of whether their approach scales to larger problem sizes.

Exact solutions to dynamic problems include a variation of the column generation approach [19], used to solve DARPs of up to 96 requests, with either static or dynamic time windows. [30] solve a PDP based on real-world logistics with multiple carriers, vehicle types and LIFO constraints using a set partitioning formulation containing an exponential number of columns. However, in general, exact methods do not scale well, so heuristic and hyper-heuristic approaches that can quickly find near-optimal solutions, have become popular for large-scale, real-world problems. [20] provides a good overview of exact and heuristic methods for vehicle routing problems. More recently, heuristic approaches have been applied to scheduling with LIFO loading constraints [3, 9, 11].

[9] use a three phase approach. First, multiple routes are created using a greedy randomised adaptive search procedure; next variable neighbourhood descent (VND) applies local search to derive new solutions using a diversification strategy derived from [26]. Finally, crossover is used to combine solutions to form further candidate solutions. [3] use a multi-start tabu search approach that uses Clarke and Wright savings [10] as well as two random schedule heuristics to build seed routes. The tabu search improves solutions by repeatedly removing and re-inserting consignments, using traditional strategies to prevent cycling and promote diversification.

Existing approaches to dynamic scheduling of PDPs (summarised in [8]) often use a two-phase hyper-heuristic [5]: requests are first inserted into a schedule, then optimisation is performed, either on a route that has been changed or on an entire schedule. Research has focused on different insertion, removal and local search operators, and on the heuristics that choose between operators at any point. For example, [17] use neighbourhood search heuristics and ejection chains to tackle same-day courier PDP. [22] use a double horizon approach with routing and scheduling sub-problems to schedule similar problems of a larger size. [1] use probabilistic information to inform their routing of a multi-period VRP.

We are concerned with efficient solution of scheduling under just-in-time logistics, where the customer expectation is that hauliers respond quickly to delivery requests, and where same-day delivery often attracts premium payment rates. In the traditional approach used by small haulage companies, static scheduling is re-run daily. However, static scheduling cannot be used for real-time response to orders, and does not take account of the existing schedule and loading. We propose a dynamic scheduler that intelligently adapts to incoming requests, a novel variant of dynamic PDP [5].

Our model of the PMDP is based on the generic PDP model of [13]. Our variable neighbourhood descent with memory (VNDM) hyper-heuristic takes inspiration from the hybrid variable neighbourhood tabu search (VNTS, [2]), which outperforms tabu and variable neighbourhood approaches for static VRPs. A schedule is built up by repeatedly inserting requests then performing optimisation. The strict LIFO constraint in PMDP, along with constraints such as the vehicle capacity, makes it difficult to find improving moves in PMDP, so we develop a descent based algorithm and local search operators tailored to PMDP, with roots in classic VRP and PDP solutions. Once a solution has been built, we perform optimisation whilst aiming to minimise ordering inversions within a vehicle’s schedule, as these are unlikely to improve results in problems with tight time windows and LIFO constraints on deliveries. Local search techniques that affect delivery order, such as those presented by [28] and [7], and the GENI technique [18], are unsuitable for direct use on our problem because they cause large changes in schedule ordering.

3 Model

The PMDP is defined on a directed graph $DG=(N,A)$ where A is the arc set and N is the node set. Each request r is identified by ($n_r$, $l_r$, [$t^{start}_{r}$, $t^{end}_{r}$], $tt^{service}_{r}$) where $n_r$ is the location, $l_r$ is the load (where the summation of pickup load and delivery loads for a consignment is equal to zero). [$t^{start}_{r}$, $t^{end}_{r}$] represents the start and end times of the arrival window respectively where the service time $tt^{service}_{r}$ must begin (for clarity we use double letters to represent quantities). R is the set of requests where $R=P \cup D \cup O$, P being the set of pickup-requests and D the set of delivery-requests. O is the set of origins which are dummy requests used to represent the multiple depot locations of the problem. The arc between two requests r and u (that is, between nodes $(n_r, n_u)$) is the arc (r, u). A consignment c is identified by ($p_c$, $D_c$, $t_c$) where $p_c$ is the pickup-request and $D_c = d_c^{1}$, $\ldots$, $d_c^{nc}$ is the sequence of delivery-requests. Each consignment has a received time $t_c$, which is the time at which the order is entered in the system. C is the set of consignments. $A_k \subset A$ represents the feasible arcs for vehicle k. The binary flow variable $b_{ruk}$ is set to one if arc $(r,u) \in A_k$ is used by the vehicle k, and to zero otherwise. $ll_{rk}$ is the load of vehicle k at request r and is not fixed but dependent on the other arcs in the vehicle’s route. It is calculated as a running sum where each request either adds to the load (pickup) or subtracts from the load (delivery). A vehicle starts and ends its route at one of the depots with load equal to zero.

The goal is to minimise the total cost of servicing all requests $r \in R$:

$$\begin{aligned} \text {min}\sum _{k\in K}\sum _{(r,u)\in A_k}C_{ruk}*b_{ruk} \end{aligned}$$

(1)

where:

$$\begin{aligned} C_{ruk} = nc(nn_{ru},ll_{rk})+tc(ruk)+dc(tt^{delay}_{uk}) \end{aligned}$$

(2)

subject to the constraints in Sect. 3.1. $C_{ruk}$ is the cost of vehicle k servicing (r, u), calculated using running cost estimations for a 44-tonne articulated truck based on 2014 data from the UK Road Haulage Association (RHA) [14]. The component costs are: $nc(nn_{ru},ll_{rk})$, the cost of travelling distance $nn_{ru}$ (the length of arc (r, u)) with load $ll_{rk}$; $tc(ruk)$, the cost of the time taken by vehicle k to travel arc (r, u); and $dc(tt^{delay}_{rk})$, the cost of the penalty for arriving late at request u. We use a stepwise function (increasing every hour) after an initial grace period, in line with industry practice. Consignments may be either customer orders or backhauls (post-delivery return to pickup location, for instance to dispose of packaging), these differ only in that backhauls are usually mostly empty loads.

3.1 Constraints

The constraints for the PMDP are laid out in Tables 1 and 2. The constraints in Table 1 have been adapted and expanded from the formulation for the PDP presented by [13]; Table 2 presents the additional new constraints for the PMDP.

Table 1. Adapted constraints from [13], here $\equiv$ implies that this constraint is equivalent to a constraint presented by Desaulniers et al. and $*$ implies that this constraint has been modified for the PMDP.

Table 2. New constraints for the PMDP.

Constraints (3) and (4) ensure that each arc is only included once and that a pickup and all its corresponding deliveries are handled by the same truck. Here, $|D_u|$ is the number of delivery-requests for pickup-request u. Constraint (4) is non-standard for the PDP and is necessary as there may be multiple delivery-requests per pickup-request. It states that for each pickup request there exists a $b_{ruk} = 1$ and that this multiplied by the number of deliveries is the same as the number of arcs that end at each of the corresponding delivery requests. Unlike [13], we are not interested in multicommodity flow, so we omit constraints (5) to (7). Constraint (8), imposing total schedule duration, remains unchanged. Constraints (9) and (10) have been modified to allow for soft time windows. Constraints (11) to (13) specify that a pickup node must have positive load and that deliveries must have negative load, also that the sum of pickup and delivery loads is zero. The initial vehicle load, non-negativity and binary requirements are the same as [13]. The following constraints have been added for the PMDP: (17) and (18) specify that a request has exactly one pickup and may have arbitrarily many deliveries. (19) specifies the precedence between a pickup and its deliveries while (20) expresses the LIFO constraint. Finally, (21) specifies that the length (in time) of any vehicles route is less than a value $E_{k}$ which may be set according to local conditions.

Minimising k, the number of vehicles used, is not considered as part of this problem, though it is kept low as a side effect of the heuristics used. For each truck, requests may be nested within other requests if LIFO and capacity constraints are not violated.

4 Solution Approach

Our PMDP solution, Like other hyper-heuristic approaches, is a two-phase process. An initial set of routes is built using a greedy constructive heuristic and then optimised with the variable neighbourhood descent with memory (VNDM) hyper-heuristic. This manages a set of low level heuristics (LLHs), introduced in Sect. 4.3.

4.1 Constructive Heuristic

As consignments enter the system dynamically and are not known in advance, the insertion heuristic treats each consignment atomically, finding the lowest cost insertion location across all routes for a pickup and all its deliveries (guaranteeing LIFO), such that no previously inserted consignment incurs a delay. This process is a greedy exhaustive search over all potential insertion locations and the position with the lowest cost is chosen.

4.2 VNDM Hyper-heuristic

After the insertion of each new consignment, VNDM is used for optimisation, running for a constant amount of CPU time. A fixed CPU time is used as there is no need to find a global optimum when new consignments that arrive will force changes to any schedule created. VNDM is a descent-based first-improvement heuristic. Routes are first ordered by length, then each LLH generates a list of potential moves. Since the majority of a schedule is unaltered after a modification, VNDM limits revisiting parts of the search space by maintaining a record of LLHs that give no improvement on each route (pairs of route and LLH identifiers are stored). If a LLH fails to produce an improving move, it is added to a tabu list. The tabu list is re-initialised when a route is subsequently modified, as a LLH may now be able to find improvement where none was previously possible.

VNDM differs from other published PDP solution approaches in a number of ways, notably in the choice of local moves used (specific to the PMDP), the use of route ordering to focus the search on promising areas, and the use of a route memory to reduce repeated searching. The search space is further reduced by imposing distance and time limits on nodes chosen for potential moves, which are different for each LLH and determined through extensive testing.

4.3 Low-Level Heuristics

The nature of PMDP, with strict LIFO ordering of consignments, guides our selection of LLHs to apply to route optimisation. Since a pickup request must occur before its delivery requests, reversing a section of a schedule and repairing infeasible pickup / delivery ordering will significantly alter the distance of the route. Because time windows are usually tight, increased distance may result in significant delay in servicing requests.

In selecting LLHs to modify routes, a consignment may only be rescheduled if the modification results in a valid schedule. A consignment may be scheduled such that other pickups or deliveries occur between the consignment’s pickup and final delivery, providing load and LIFO constraints are not violated. However, if the consignment is rescheduled, the nested pickups or deliveries from other consignments remain in the original schedule, thus allowing modifications to undo nested consignments.

Highly disruptive LLHs that introduce partial route inversions cannot improve our schedules as these would invalidate either the LIFO or precedence constraints of pickups and their deliveries. This rules out LLHs such as GENI [18] and iCROSS [6]. However, we can use the CROSS exchange of [27] (used by [28]) as it does not reverse chains of requests. Additional LLHs, such as GENI-PO [23], have been chosen or developed to preserve existing schedule ordering as much as possible. By keeping the pickup and deliveries of one consignment in the same schedule (rather than splitting the consignment across loads and using precedence constraints), we facilitate the use of LLHs from the widely-researched area of one-many-one VRPs [7].

We provide four LLHs that can be applied to a single route. If a single route operator can generate more than one resulting route, that which is least disruptive to existing schedule ordering is used. LLHs that would reverse the order of a chain of requests are not allowed, hence we do not use 2-Opt.

3-Opt moves one consignment to a different position in the route schedule, whilst 4-Opt swaps the positions of two consignments in the route schedule. Nest Consignment moves a whole consignment to a position within the delivery schedule of another consignment, thus nesting the first consignment within the second. Finally, Nest Two Consignments nests two consignments inside other consignments, a useful move where single-level nesting produces no improvement.

We provide four further LLHs that operate on more than one route at a time. GENI-PO [23] is a non-inverting variant of GENI [18]. The other three LLHs are from [27]. Relocate moves one consignment to a valid position in a different route schedule, which may introduce nesting. Geni-PO is a variation of relocate that preserves as much previous ordering as possible by moving a consignment to be geographically close to other consignments: all possible insertion position pairs are considered to find the most improving relocation. Swap exchanges consignments from two different routes, whilst Cross exchanges two chains of consignments between routes, preserving the existing ordering within each chain. Cross considers chains of all lengths when used.

Use of Local Moves. Of the eight LLHs, three consume only small amounts of CPU time for problems of the size we study (3-Opt, 4-Opt and Nest consignment), whilst the others (Nest two consignments, Relocate, Geni-PO, Swap and Cross) are considered hard and take a significant amount of time. However, the hard LLHs generate several orders of magnitude more potential moves than the computationally trivial moves. There is no intuitive reason to prefer one hard LLH to another, and there is little advantage to running more than one hard LLH at a time. Thus, to prevent VNDM optimisation simply running out of time whilst applying too many hard LLHs, each call of VNDM uses a neighbourhood structure comprising the three low-CPU LLHs in the order above, then one hard LLH, selected at random. The random selection ensures that all the hard LLHs are used over a series of optimisations, and thus provides ample diversification.

5 Computational Results

In collaboration with Transfaction Ltd., we have access to real scheduling data and manually-scheduled consignments for small UK hauliers (referred to as real data). The real data are insufficient, in quantity and quality, for our scheduling research, but provide us with indicative distributions and other information, from which we generate larger, realistic, data sets on requests and consignments (referred as generated data).

We generate 100 scenarios from a data set of 27,153 real-world consignments. The scenarios are built by selecting 200 real consignments at random from this set and building pairs of consignments representing outbound linehaul and return backhaul legs. Each consignment consists of at least two requests.

Initially, each haulage company (carrier) is assumed to have an unlimited number of vehicles and is represented by a depot, randomly located within the area encompassing the consignments. Consignments are assigned to the carrier, from the set of carriers with the fewest consignments, that is geographically closest to the midpoint between a consignment’s pickup and final delivery locations. Thus, the initial schedule systematically distributes consignments evenly across many carriers. To analyse a dynamic system in silico, we use discrete event simulation.

5.1 Discrete Event Simulation (DES)

DES [25] is used to simulate the dynamic receipt of consignment requests. In order to add new consignments to a schedule that is already being serviced, we keep track of simulation time (an internal representation of current time, stored so that requests which in reality would have already happened cannot be modified by our optimisation procedure). If the scheduled start time of any request is before the current simulation time, it is marked as “fixed”. Additional requests cannot be inserted before these fixed requests, and the routing of a fixed request cannot be altered in any optimising moves.

For each experiment we simulate one dynamic scheduling week, and limit optimisation to 5 min of CPU time. Each scenario is run 30 times, using a heterogeneous cluster of Intel Xeon based servers, totalling 72 cores and 120GB of RAM. The results presented here thus represent thousands of CPU hours.

5.2 Simple Cooperative Strategies

The first set of results compares the average per request costs for five carriers, exploring the effect on one carrier (the sample) under four different configurations of cooperation with the other four carriers. All Contracted has each consignment assigned to a specific carrier. Optimisation is only possible between vehicles belonging to the same carrier. Out-sourcing starts with a competitive model, but allows re-assignment of consignments from the sample to any of the other carriers, if cost savings can be made. Out-sourcing to coop(erative) adds the out-sourcing model for the sample carrier into a model in which the other carriers can exchange consignments if savings can be made; the sample carrier does not accept any additional consignments. Finally, the cooperative model initially assigns all consignments to individual carriers (as in Contracted) but allows unrestricted re-allocation during optimisation, if cost savings are possible.

Fig. 1.

Average cost for a single carrier (sample carrier) and a group of carriers (other carriers), with four different models of cooperation.

The costs presented in Fig. 1 show that for the sample carrier, an average 9% saving can be made by out-sourcing to the four other carriers, whilst the configuration that allows other carriers to also cooperate results in average savings of nearly 14%, because the cooperation allows more efficient routing across the carriers. If the sample carrier also cooperates in efficient scheduling, the total average saving for the sample carrier rises to 18%. Cooperation is also beneficial for the other carriers: accepting orders from the single carrier can produce benefits of 3%, whilst cross-group cooperation produces savings to averaging 15%.

The results shown should drive all carriers towards cooperation. Competition favours carriers with the lowest costs; the sample carrier achieves this in configuration 2, by outsourcing to other carriers who are not cooperating. However, rational competitors would be expected to copy this behaviour, moving the system towards a reallocation of consignments as seen in configuration 3; here, the competitors are cooperating, and the sample carrier is at a competitive disadvantage. However, if all carriers cooperate, as in configuration 4, the lowest costs for all carriers are observed.

Increasing cooperation allows a greater number of consignments to be handled. Figure 2 shows that the schedule in which all carriers operate alone covers on average less than 70% of their assigned consignments. However, the fully cooperative model can schedule over 85% of consignments. (Note that random scenario generation means that there is no guarantee that all consignments are feasible given the number of carriers, their locations and that even with an infinite number of vehicles, some consignments are too far apart to be serviced whilst adhering to driver working hour rules: since we do not consider driver sleeping arrangements and all routes must begin and end at the depot, these consignments are impossible in our current model.)

Fig. 2.

Percentage of assigned consignments serviced across the four different models of cooperation.

Table 3. Percentage of the sample carrier’s consignments re-allocated in different configurations.

Table 3 shows the percentage of consignments that are re-allocated from the sample carrier in each configuration. Both out-sourcing and out-sourcing to a cooperative allow almost two-thirds of the carrier’s consignments to be assigned to others: because our scheduling algorithm minimises cost, these re-allocations can be interpreted as being carried more cheaply, due to more efficient use of resources, when assigned to other carriers. We are most interested in the percentage of consignments that are re-allocated away from the sample carrier. When outsourcing and cooperation are combined (configuration 3), the sample carrier’s re-assigned loads are most cost-effective, as, in this configuration, the other carriers can also re-allocate loads among themselves (but not to the sample carrier). In the fully cooperative model, the sample carrier’s consignments are less cost-effectively reassigned than in other reallocation configurations. However, the overall cost-effectiveness of the 5 carriers is significantly better than in other configurations: 62.5% of other carriers’ consignments were reallocated in this model, leading to the reduction in cost observed for cooperation in Fig. 1. These results also strongly support the contention that savings can accrue to small hauliers who cooperate to carry each others’ consignments efficiently.

5.3 More Group Configurations

We seek to further investigate the effects of different sized groups of carriers on both cost and network capacity. Using the same 100 scenarios as investigated previously, we now investigate how efficiently 10 carriers can service the consignments, split into a number of different group configurations. Cooperation is allowed within but not between these groups. In the Competing configuration each of the 10 carriers works independently, in the second configuration, carriers work in Pairs. In 1 vs 3s, one carrier, the sample, is compared against 3 groups of 3 carriers. In 5 vs 5, 3 vs 7 and 1 vs 9 the 10 carriers are divided into 2 groups of differing sizes accordingly. In the final configuration, Cooperative, the 10 carriers work together.

Fig. 3.

Cost per request for different carrier group configurations.

Figure 3 confirms our earlier findings that working as a group can substantially reduce costs and additionally shows that larger groups can attain bigger cost reductions than smaller groups.

In each configuration, consignments are divided equally between groups, not carriers, such that, for example in the 1 vs 3s configuration each group of carriers is assigned 100 consignments out of 400 but in the 1 vs 9 configuration, each group is assigned 200 consignments. Because of this, carrier 1 has more choice in the 1 vs 9 configuration and can achieve slightly better results than in the 1 vs 3 s configuration, however the number of consignments that can actually be served is dramatically reduced as can be seen in Fig. 4.

Fig. 4.

Percentage of scheduled consignments for different carrier group configurations.

Figure 4 shows again the increase in network capacity made possible through cooperation. It is also clear that the largest savings are made quickly: just pairing with one other carrier can increase the number of scheduled deliveries from 72% to 80%.

5.4 Carrier Group Size

Extending our analysis, we seek to identify if there are diminishing returns for increasing the number of carriers in a cooperative group. Figure 5 shows how both the cost per request and the percentage of consignments scheduled improve as the size of a cooperative group increases. Though there are linear savings evident above 10 carriers, the majority of benefit is found between 1 and 5 carriers. These results must be qualified by stating that our consignments cover the UK and our carriers are randomly located across this area; since distance costs are a dominant factor in real-world pricing; if larger distances are involved, for instance across Europe, America or Asia, a larger number of well distributed carriers would likely be necessary to produce these savings. These results can be thought of more as suggesting that 10 major transport hubs is sufficient for efficient vehicle routes in the UK.

Fig. 5.

Cost per request and number of consignments successfully scheduled as the number of carriers working together increases.

So far, we have assumed an infinite number of vehicles at each carrier location; in practice there will be a limited supply of vehicles at each carrier and therefore multiple carriers in the same area would need to work together. The following section investigates cooperation in resource constrained situations.

5.5 Competition

The experiments so far have assumed an infinite number of vehicles available for all carriers and looked at cooperation from the assumption that all companies work together to reduce total costs. We use the same 100 scenarios each with 10 carriers and 200 orders (assigned as before). However, companies now have a fixed number of vehicles. If a company cannot satisfy an order assigned to it, instead of creating additional vehicles, the customer is re-assigned to a random company that can service it. This means that a better utilisation of assets will lead to more customers for a given company. We also introduce a model for order revenue, enabling us to estimate carrier profitability. We assume that companies will not share their orders if it results in them loosing money, therefore, when cooperation is allowed between two companies, the company originally assigned an order always receives the profit it would make. For a different company to fulfil this order, it must yield sufficient profit to pay off the original company and still cover the associated delivery costs. The revenue model for an order is:

$$\begin{aligned} \text {Revenue}(c) = l_{p_c}\sum _{r\in D_c}nn_{r-1,r} \end{aligned}$$

(22)

where the revenue of consignment c is a linear function of the total distance between all requests in the consignment multiplied by the pickup load. A company’s total profit is the revenue of all the consignments it delivers minus the total cost of serving these, as specified in Sect. 3.

We now consider variants of the scenarios previously investigated, but, in each case, the number of vehicles is fixed at 40. We consider the impact of cooperation in scenarios with different distributions of these vehicle between the 10 companies, to simulate different competitive environments.

Equally Sized Companies. First, to validate our previous findings the 10 companies are set to have equal size, with 4 vehicles each. As expected, Fig. 6 shows that cooperation increases the profitability of all companies.

Fig. 6.

Effect of cooperation on the total profits for ten equally sized companies.

Differently Sized Companies. The ten companies are now given different numbers of vehicles, set to: “2, 2, 3, 3, 4, 4, 5, 5, 6 and 6” respectively. Figure 7 shows the increased profitability of the first three companies when they work together as a cooperative assuming that all other companies continue to work independently. Profit increases of 12–18% demonstrate that even the smallest companies benefit from cooperation.

Fig. 7.

Effects of cooperation between small companies.

Looking at the group of heterogeneously sized companies in more detail, Fig. 8 shows how company size affects both raw profitability and the benefit of cooperation. Larger companies are able to produce more optimal routes and service more customers, generating more profit. When all parties cooperate, the profits for companies of all sizes increases. We can see that, as a percentage, small companies stand to gain the most from working cooperatively, with gains of up to 50%. Compared to the 12–18% result, above, it is again clear that more companies working together produces better results.

Fig. 8.

Effects of cooperation across different sized companies.

Large Vs Small Companies. In this scenario we compare the profitability of large and small companies competing in the same market. The ten companies are now set to: “8, 2, 2, 2, 2, 2, 2, 2, 9, and 9” vehicles respectively. Figure 9 shows that, initially (when no companies are cooperating), the 2 largest companies produce the most profit. When the small companies work together they can increase their profitability and reduce the profits of the larger companies. Finally we observe that if the first large company joins the cooperative it can massively outperform its competitors. Other companies’ profits fall, and the cooperative can more effectively handle orders (so orders are not stolen by the large companies).

Fig. 9.

Profit in a scenario with large and small companies. Company 1 has 8 vehicles. Companies 2–8 have 2 vehicles each. Companies 9 and 10 have 9 vehicles each.

6 Discussion and Conclusions

We have presented the VNDM hyper-heuristic as an effective schedule optimisation for PMDP under dynamic consignment requests. The objective and ordering constraints of the problem are set out and a set of LLHs optimised for these is given. We use data from the RHA to explore pricing and marginal costs of consignments, and show that cost savings of 15% to 18% are possible when hauliers cooperate. Cooperation also increases the capacity of a group of hauliers, by as much as 21%. The benefits of cooperation see diminishing returns above 10 separate carrier locations working together assuming sufficient numbers of vehicles to meet demands. Larger cooperatives will always have lower operating costs than smaller ones as they are able to more efficiently schedule their consignments to the most optimal company locations.

We have carried out further investigation into how savings from cooperation could be turned into increased profit in resource constrained problems with a fixed number of vehicles. We propose that the revenue of a customer be modelled as a linear combination of distance and load and define company profit as the sum of revenues over all delivered consignments minus the costs associated with delivering these loads. We consider that each company aims to maximise its own profit by only reassigning customers when a cooperating company can pay off the original company’s profit and still cover its delivery costs. The cooperating company makes the cost saving as its profit on such orders. We have shown that this more realistic model of cooperation still leads to increased profits for all cooperating parties in a variety of different scenarios with differing company sizes. A particularly interesting result is that competing large companies stand to significantly benefit by cooperating with a group of smaller companies. Benefits of cooperation scale with the number of companies in the cooperative but generally lie within 15–20%.

We do not consider issues of vehicle reliability, for example, who pays the costs associated with missed delivery slots and what effect this has on customer perceptions. We have not considered the fixed costs associated with carrier-owned vehicles in this research; implementing the strategies outlined in this paper may result in reduced usage of carrier owned assets as cooperation allows for an increase in capacity, allowing the same fixed cost assets to be more productive, assuming there is sufficient demand for service.