In progress Splitting the bill of timely transportation
- ERIM ESE 2017 AW_RS_WvdH
Transportation costs of a delivery route are dependent on the total distance travelled and the time spent on the road. When multiple customers are visited on such a route, it is not at all obvious which customer is responsible for what share of the costs. Customers affect the delivery route in various ways, depending on their location, demand size, and the time window during which they wish to receive their delivery. The research described in this proposal is aimed at developing decision support tools to allocate the costs of a delivery route to the various customers. Note that depending on the application, these costs may be thought of as monetary or emission.
Researchers have in the past years recognized many opportunities for collaboration in transportation. However, in practice such initiatives are hindered by the inability of different parties to share the costs and benefits of such collaborations. To overcome this inability, in this study allocation methods will be developed to allocate costs in a way that is agreeable to all parties involved. This way, the proposed research complements many past and current research projects in this field.
To design such allocation methods, a model will be designed using concepts of cooperative game theory combined with vehicle routing. Special attention will be paid to the inclusion of time windows for delivery at each customer. Considering time windows is vital for the applicability of allocation methods. Although in many applications time windows are present, the limited body of research on cost allocation does not include these.
In the proposed research a general theoretic framework will be developed for cost allocation games. This framework will then be extended for three particular applications They are: intercompany consolidation of transport flows, computing delivery fees charged by e-grocers and allocating CO2 emission.
Operations Research, Vehicle Routing, Cooperative Game-Theory
Time frame2017 - 2021
When dining with a group of people, splitting the bill is often a simple task. Assuming that the costs of the individual meals are independent, the bill states the price of each dish and it is easy to see who is responsible for what share of the costs (although social convention usually dictates the bill is split evenly among all guests). In transportation the story is quite different. If one truck is used to make deliveries to multiple customers, it is not easy to see which customer is responsible for what share of the costs. What share of the total costs should be attributed to this customer? It is exactly the inability to answer this question which hinders collaboration initiatives in practice.
The variable costs of transportation are mostly dependent on the driven distance and time, e.g., fuel and driver salary costs or CO2 emission. As such the costs are determined by the order in which customers are visited and dependent on the distance between customers and the size of each load (more load leads to more trips). Moreover, the time of delivery that is required by each customer also affects the order of visits. Suppose for instance that customers A, B and C require their delivery in the time windows [12:00-13:00], [14:00-15:00] and [16:00-17:00] respectively. The only feasible route, A-B-C, is now completely determined by the time windows. The delivery times might prevent cheaper routes from being feasible, and are therefore an important determining factor of the total costs. Given all the interrelating customer features, the challenge is to determine the share of the total costs that can be attributed to each individual customer.
This research proposal is written with three separate applications in mind, each giving rise to unique challenges. They are: intercompany consolidation of transport flows, computing delivery fees charged by e-grocers and allocating CO2 emission. In each of these application areas, much progress has been made recently in developing decision support tools for scheduling in logistics, while current research projects are still pushing the limits. Reaping the benefits of the new technology hinges on cooperation of multiple parties. However, a major reason as to why these new technologies are not readily adopted in practice is that these different parties are unable to come to an agreement on how to share the costs and benefits of cooperation schemes. This research aims at overcoming this inability.
Although the applications, which will be elaborated on below, are relatively diverse, a common theme is clear: delivery routes are designed to visit multiple customers while the transport costs should be allocated to each customer. The crucial part here is that the allocation should be agreeable to all parties involved. To model this, concepts of cooperative game theory will be used. In cost allocation games one typically searches for an allocation that lies in the core of a game, the core being defined as the set of allocations to which no player can rationally object, i.e., no subset of customers can get a better cost allocation by withdrawing from the original delivery route and starting a separate delivery route. Several such core allocations have been studied for general games, like the Lorenz allocation (Arin, 2003) or equal profit allocation (Frisk et al, 2010), both providing an egalitarian core allocation. Another popular allocation is the Nucleolus of a game (Schmeidler, 1969), which can be considered the center of the core if it is nonempty, while it can be considered the least instable allocation in case the core is empty.
Next to allocating costs, the envisioned game involves creating delivery routes. Creating delivery routes that minimize transportation costs requires solving the vehicle routing problem with time windows, VRPTW, a classical problem in operations research. This notoriously difficult to solve optimization problem has been studied extensively and many exact and heuristic approaches to solve this problem are described in the scientific literature, see for instance Baldacci et al. (2012), Laporte (2009) and Bräysy and Gendreau (2005a and 2005b) for recent overviews. A successful method for solving the VRPTW to optimality is by branch-price-and-cut, a specific branch-and-bound procedure where linear programming bounds are computed by a column generation algorithm, see for instance Baldacci et al. (2012) and Desaulniers et al. (2008).
Routing games, i.e., games in which a delivery route is designed and the costs are allocated, have been studied in the scientific literature, see e.g. Engeval et al. (2004). However, to the best of my knowledge, no research has been done on vehicle routing games including time windows. The exclusion of time windows poses a significant barrier for applying current research in everyday practice. It therefore constitutes an important gap in the current scientific literature. Including time windows, however, is a big methodological challenge and requires the development of new allocation procedures.
The game that will be researched is to allocate costs of a delivery route. To do so, delivery routes adhering to time window constraints are simultaneously designed while providing a core allocation of the transport costs to the customers. A branch-price-and-cut approach will be endeavored to find a suitable allocation. The core is typically characterized by the transport costs of separate delivery routes for every subset of customers, which can be represented by an exponential number of linear constraints. The search for a core allocation will therefore involve the design of many delivery routes. The expectation is that computational efficiencies might be gained by employing a column generation procedure to construct the delivery routes; good routes (columns) for one subset of customers might be reused in some way for other subsets of customers. Also, it might not be necessary to include all core constraints explicitly. Therefore, separation techniques will be studied to avoid this.
Given the complexity of the game, a branch-price-and-cut procedure might yield a suitable allocation in reasonable computation time only for moderate sized problem instances. Heuristics (column generation heuristics or otherwise) will also have to be designed to find suitable allocations for larger instances.
Next, the different applications are described and the additional methodological challenges they bring are highlighted.
Intercompany consolidation of transport flows
In this application the consolidation of transport flows is considered of multiple separate companies that frequently transport goods to their customers. For instance in retail chains regular supply runs are made to each customer, which are company owned stores. Vehicles used for this are typically not filled to maximum capacity, consider e.g. the return trip to the depot. Hence there is slack capacity that might be utilized by other companies. This opportunity is recognized by many researchers, for instance in the DATAS project and the Last-Mile project (see references). While the focus in current research lies on designing decision support tools to enable and improve intercompany consolidation of transport flows from a scheduling point of view, benefiting in practice from advances in this area is hindered by the inability of companies to share costs and benefits. The game described before directly applies here, although specific structures encountered in practice should be taken into account. For instance, the players in this particular game are not the many individual customers but groups of customers corresponding to the same company.
Computing delivery fees charged by e-grocers
The market of e-grocers is typified by fierce competition and low profit margins on goods. Consumers expect groceries to be priced similarly online as in offline stores, while the willingness to pay for home-delivery is limited. E-grocers compete by asking low delivery fees, or even free delivery, while offering high service such as delivery within an increasingly narrow time window of the customers’ choosing. The low profit margins on the products are not sufficient to cover the incurred delivery costs. Therefore, to be economically viable a delivery fee must be charged to the customer. The envisioned allocation method is able to divide costs among the customers reflecting the service that they choose, e.g., the choice of home delivery time window. This allows for economic sustainability of e-grocers.
A big challenge in computing delivery fees in this setting is that customers arrive dynamically. When a customer places an order, the total transport costs are not yet known since not all orders are placed yet, while the customer needs to be quoted a delivery fee.
Allocating CO2 emission
Alternative to allocating monetary costs, also CO2 emission might be allocated to customers. Next to government regulations and consumer pressure, many initiatives exist of transport companies imposing emission targets on themselves, e.g., Smart-Way U.S., Green Freight Europe and the Dutch Lean and Green program. To successfully implement these initiatives a precise measurement of emission per company is crucial, requiring the allocation of CO2 in case of intercompany collaboration. In Naber et al. (2015) the results of the study of a single delivery route emission allocation game are presented. However, we did not include time window considerations, a severe limiting factor of the applicability. Another important challenge in this setting is that the routes are typically designed to minimize monetary costs while CO2 is allocated, which affects the design of a model and allocation procedure.