Cost Allocation in Vehicle Routing Problems with Time Windows

Arroyo, Federico Article Cost Allocation in Vehicle Routing Problems with Time Windows Junior Management Science (JUMS) Provided in Cooperation with: Junior Management Science e. V. Suggested Citation: Arroyo, Federico (2024) : Cost Allocation in Vehicle Routing Problems with Time Windows, Junior Management Science (JUMS), ISSN 2942-1861, Junior Management Science e. V., Planegg, Vol. 9, Iss. 1, pp. 1241-1268, https://doi.org/10.5282/jums/v9i1pp1241-1268 This Version is available at: https://hdl.handle.net/10419/290634 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Junior Management Science 9(1) (2024) 1241-1268 Junior Management Science www.jums.academy ISSN: 2942-1861 Edi tor: DOMINIK VAN AAKEN Adv isory Editorial Board: FREDERIK AHLEMANN JAN-PHILIPP AHRENS BASTIAN AMBERG THOMAS BAHLINGER MARKUS BECKMANN CHRISTOPH BODE SULEIKA BORT ROLF BRÜHL KATRIN BURMEISTER-LAMP JOACHIM BÜSCHKEN CATHERINE CLEOPHAS NILS CRASSELT BENEDIKT DOWNAR RALF ELSAS KERSTIN FEHRE MATTHIAS FINK DAVID FLORYSIAK GUNTHER FRIEDL MARTIN FRIESL FRANZ FUERST WOLFGANG GÜTTEL NINA KATRIN HANSEN ANNE KATARINA HEIDER CHRISTIAN HOFMANN SVEN HÖRNER KATJA HUTTER LUTZ JOHANNING STEPHAN KAISER NADINE KAMMERLANDER ALFRED KIESER NATALIA KLIEWER DODO ZU KNYPHAUSEN-AUFSESS SABINE T. KÖSZEGI ARJAN KOZICA CHRISTIAN KOZIOL MARTIN KREEB TOBIAS KRETSCHMER WERNER KUNZ HANS-ULRICH KÜPPER MICHAEL MEYER JÜRGEN MÜHLBACHER GORDON MÜLLER-SEITZ J. PETER MURMANN ANDREAS OSTERMAIER BURKHARD PEDELL MARCEL PROKOPCZUK TANJA RABL SASCHA RAITHEL NICOLE RATZINGER-SAKEL ASTRID REICHEL KATJA ROST THOMAS RUSSACK FLORIAN SAHLING MARKO SARSTEDT ANDREAS G. SCHERER STEFAN SCHMID UTE SCHMIEL CHRISTIAN SCHMITZ MARTIN SCHNEIDER MARKUS SCHOLZ LARS SCHWEIZER DAVID SEIDL THORSTEN SELLHORN STEFAN SEURING ANDREAS SUCHANEK TILL TALAULICAR ANN TANK ORESTIS TERZIDIS ANJA TUSCHKE MATTHIAS UHL CHRISTINE VALLASTER PATRICK VELTE CHRISTIAN VÖGTLIN STEPHAN WAGNER BARBARA E. WEISSENBERGER ISABELL M. WELPE HANNES WINNER THOMAS WRONA THOMAS ZWICK Volume 9, Issue 1, March 2024 JUNIOR MANAGEMENT SCIENCE Paul Sunzenauer,How Sustainable Is Private Equity? Unlocking the Impact of Private Equity on AssetLevel Sustainability: An Empirical Investigation Fabienne Le, How Do Companies Communicate Sustainability: A Semantic Analysis of German Automotive Manufacturers Frédéric Herold, Flipping the Switch –The Role of Activity Load in Temporal Acquisition Patterns of Acquiring Firms Patrick Riedlsperger, Decarbonizing Travel Decisions by Using Digital Nudges Jan Keim, Depolarizing Innovation: Dynamic Policy Implications for Entrepreneurial Ecosystems in Second-Tier European Regions Federico Arroyo, Cost Allocation in Vehicle Routing Problems with Time Windows Maryam Rassouli-Baghi, Rewarding Creativity: The Moderating Role of Personality Paolo Oppelt, The Effect of Carbon Taxes on Directed Technological Innovation: A Case Study of Sweden Faris Ben Saad, How to Measure the Success of TechnologyBased Start-Ups –A Comprehensive Overview of the Perspectives of Academics & Practitioners Lea Krähenmann, Self-Optimization for Individual Happiness? 1100 1123 1140 1178 1211 1241 1269 1286 1306 1341 Published by Junior Management Science e.V. This is an Open Access articl e distributed under the terms of the CC-BY-4 .0 (Attribution 4.0 I nternational ). Open Access funding provided by ZBW. ISSN: 2942-1861 Cost Allocation in Vehicle Routing Problems with Time Windows Federico Arroyo Technical University of Munich Abstract The estimation of costs allocated to each customer when serving them in a collaborative logistic operation is a complex problem whose solution is computationally very expensive. In this work the case of central horizontal collaboration for vehicle routing problems with time windows and a central depot is studied. An approximation to the Shapley value method via structured random sampling is used to calculate the cost associated with customers in Solomon instances. Such costs are regressed to a linear model with a set of defined features. The results show that cost can be predicted with considerable accuracy with few features. Moreover, the extent to which vehicles’ capacity, customers’ demand and distance, the degree of customer clustering and time window horizons affect cost and potential savings from carriers in collaboration is assessed. Additionally, individual regression models of different set of instances show how various pricing strategies for customers can be fitted to their classification when grouping them. Keywords: collaborative vehicle routing; cost allocation; Shapley value method; structured random sampling; time windows 1. Introduction 1.1. Context and motivation With the world’s population continuing to grow and an ever-expanding international commerce, logistics networks become increasingly complex. The supply chain, as a means of delivering products from manufacturers to customers, comprises the interactions between enterprises involving a multi-organizational network adding value to the flow of information, logistics and capital (Leng et al., 2018; Tang et al., 2022). It is within this operation that any potential for improvement brings substantial value. I would like to express my gratitude to Prof. Dr. Stefan Minner for affording me the invaluable opportunity to compose my master thesis under his supervision and mentorship. His continuous provision of insightful suggestions, innovative ideas to enhance my thesis, and unwavering support during the writing process have been truly instrumental. Furthermore, my appreciation extends to the esteemed Chair of Logistics and Supply Chain Management of the Technical University of Munich where I was given full assistance and support along my studies and in preparation for my thesis. Lastly, I extend my thanks to family and friends, whose steadfast encouragement and caring have been a driving force behind my endeavors, fostering both my personal and professional growth. Further, the mass adoption of the internet, in conjunction with the development of new technologies, has made online shopping a very comfortable means for consumers to acquire their products, favoring it in many cases over brickand-mortar shops. This change of behavior towards ordering products online has meant rapid growth for e-commerce which has been further exacerbated by the COVID-19 pandemic, feeding the need for more retailers online and the growth in deliveries (Alfonso et al., 2021; Jílková & Králová, 2021). The final leg of the logistics problem, known as the last mile, is where retailers and logistic carriers mostly find their costs increasing due to the inefficiencies of the industry (Iannaccone et al., 2021). This operation of delivering a parcel from the last hub to the customer accounts for 28 % of the total logistic cost (Ranieri et al., 2018). Moreover, the effect of increased urban parcel demands in the context of urbanization can be very harmful to cities. With 70 % of the world’s population expected to live in cities by 2050, the impact on the environment, safety and health from pollution and congestion becomes even more important (Bretzke, 2013). Consequently, public institutions and governments are beginning to regulate carriers’ operation more intensely, pushing for inDOI: https://doi.org/10.5282/jums/v9i1pp1241-1268 © The Author(s) 2024. Published by Junior Management Science. This is an Open Access article distributed under the terms of the CC-BY-4.0 (Attribution 4.0 International). Open Access funding provided by ZBW. F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681242 creased sustainability and efficiency in their operations (Hu et al., 2019). With regards to the timing of deliveries, firsttime delivery failures have been reported up to 60 %, resulting in a significant cost for carriers (Song et al., 2009). Additionally, same-day deliveries and the expectations coming from customers of receiving their parcels fitting their schedules compel agents to work with tight time horizons. Within this context, companies are either forced or need to collaborate with each other to remain competitive and streamline their costs. Horizontal collaboration appears as an effective solution for carriers to increase their operational efficiency (Gansterer & Hartl, 2018b). For this reason, it is increasingly important for public agents in the last years (Cruijssen & Cruijssen, 2020). In a sharing economy, where companies are using common resources and capacities in urban areas to provide new services, new business models emerge and traditional ones need to innovate in order to continue doing business (Dahle et al., 2019). 1.2. Problem statement In recent years, the area of collaborative vehicle routing has gained great popularity in transportation and logistics research (Gansterer & Hartl, 2020). Shared transportation resources define the base concept where different partners join in a common operation. In the realm of collaborative vehicle routing, we focus on those problems with capacity and time constraints, later explained in Section 3.1. To cope with the growth of deliveries and the ever-tightening constraints of time and capacity, collaborative environments allow for a great level of optimization within logistic operations (Karaenke et al., 2019; Vanovermeire et al., 2014). In this regard, there is a strong incentive for carriers to participate in a joint coalition given the cost reductions they can achieve (Muñoz-Villamizar et al., 2015). Moreover, through the optimized use of resources, companies can benefit from providing better service, due to their increased flexibility and better times of delivery (Cruijssen, Dullaert, & Fleuren, 2007). Additionally, there is a need for them to decrease their environmental impact. In the USA, for example, it has been found that logistics vehicles can travel totally empty in up to 15% to 20% of the distance they cover (Ferrell et al., 2020). Companies, therefore have the motivation to increase their sustainability and their reputation. Within the paradigm of companies cooperating and sharing resources, we focus on horizontal collaboration where carriers belong to the same level of the supply chain. Vertical collaboration, on the other hand, involves other levels in it. A common understanding, represented through a central system or platform, is needed for agents to interact and plan together horizontally, with some cities already introducing such systems (Schmelzer et al., 2016). The way collaboration structures are defined is crucial to allow for horizontal collaborations to prosper due to competitors being reticent to share their information and resources for lack of trust (Bratton et al., 2000). Transparency and confidentiality are key for competitors not to fear their strategic advantage is threatened. Consequently, having a fair distribution of costs arisen and profits obtained is of greater importance for the stakeholders involved (Cruijssen, Cools, & Dullaert, 2007). In this regard, our work is centered in cost allocation in collaborative vehicle routing problems, where the total cost of a global operation needs to be divided between the individual carriers. The objective is to assign costs to each of the customers that each partner brings into the coalition in a simple but fair way. The cost allocation method must assure that no partner perceives their allocated cost as being too large, for they risk the stability of the cooperation. We explore this in Section 3.2. The numerical complexity of the problem calls for the search for simpler mechanisms which is at the center of our work. 1.3. Research question and thesis outline Given the scope presented, we aim at answering the following question: Can cost allocation mechanisms in vehicle routing problems with time windows be approximated through simple methods? With this, we determine the accuracy of a simple costallocating linear model where certain features are used to address the variables of the problem. Additionally, by using different instances with different degrees of clustering and time window horizons, we analyze the impact these dimensions have on the cost-allocating process and derive conclusions for different pricing strategies. Concerning the allocation mechanism itself, we determine the degree to which the allocating results are advantageous for all carriers and whether or not all customers yield savings when shared with others. This work begins by reviewing the available literature on the subject and summarizing basic definitions in Section 2. The methodology to tackle the problem in question is defined in Section 3 where the modelling and solving of vehicle routing problems, cost-allocating mechanisms and regression methods are presented. Later, in Section 4, the analyzed instances and cost function features are introduced. Subsequently, the results obtained are analyzed in Section 5. This comprises an overview of the costs allocated to each customer for the different instances, followed by the model fit and feature selection and the study of collaborative gains. To finalize, conclusions and recommendations for future research directions are pointed out in Section 6. 2. Literature review In the context of our investigation, we begin our work by thoroughly reviewing the current state of academic research concerning cost allocation in collaborative multi-carrier vehicle routing problems with time windows. To better digest the subject, we focus on the two main bodies of research that our study focuses on. On the one hand, we start by evaluating the vehicle routing problem and its variations; focusing on horizontal collaboration. Further, we describe the related F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1243 work in the area of cost allocation methods for collaborating logistics. We aim to present the known sources on which we base our work, finding potential unexplored areas in research that we intend to develop. 2.1. The vehicle routing problem The Vehicle Routing Problem (VRP), introduced by Dantzig and Ramser (1959) and Clarke and Wright (1964), still remains one of the most widely studied problems in operations research (Kritikos & Ioannou, 2010). It consists of a family of problems in which a set of customers with known demands and geographical location have to be served by a fleet of vehicles based at one (or many) depot(s) through a network of paths between them. The task is to determine the optimal set of routes for the vehicles which achieve the objective and satisfy the constraints imposed on the problem (Irnich et al., 2014). Multiple variations and extensions to the VRP have been introduced which are mainly classified based on their objectives and constraints (Laporte, 2009). Most commonly, a capacity restriction is imposed on the vehicles, with each location having a specified demand quantity. This problem, known as the Capacitated VRP (CVRP), imposes that each customer needs to be served only once and the capacity of vehicles is not surpassed by the total amount of customer demands served by the vehicle in its route (Goel & Gruhn, 2008; Prins, 2004). Additionally, the CVRP with Time Windows (CVRPTW) introduces the time dimension and the constraint of customers being served in a time interval, also known as Time Window (Kallehauge et al., 2005). The addition of several depots with multiple pickup and delivery points (Berbeglia et al., 2007) as the discrimination between full truckload and less than truckload (Gansterer & Hartl, 2018b) are also well-known alternatives that we will not explore in our work. When several carriers are present, each of them having to solve a VRPs by their own, potential benefits have been found when collaborating in a joint logistic operation, originally reviewed in (Cruijssen, Dullaert, & Fleuren, 2007; Krajewska & Kopfer, 2006). In their survey, Gansterer and Hartl (2018b) show that problems in vehicle routing in a collaborative scenario can be addressed from a central or decentral planning perspective. Central plans require the intervention of one decisionmaker who is fully informed. The information provided for each carrier can consist of cost structures, capacities and information on existing customers (Gansterer & Hartl, 2018b). An example of this in digitalized times would be an online platform/database where carriers’ requests are shared and solved in a logistics problem. In this situation, the problem is reduced to a holistic standard optimization problem where all resources are bundled and the collaborative aspect is overtaken by the full disclosure of information. In decentralized collaborations, carriers are able to share their capacities to a certain extent by revealing a limited amount of information. In said setting partners may deal individually with each other or channel their requests through a central authority. Studies on this area are presented by (Berger & Bierwirth, 2010; Dai & Chen, 2011; Gansterer & Hartl, 2018a; Gansterer et al., 2019; Krajewska & Kopfer, 2006; Özener et al., 2011), covering non-auction and auction-based mechanisms for the selection and exchange of requests. As reviewed by Gansterer and Hartl (2018b), when it comes to real-world cases the potential collaboration gains have been calculated up to 20%-30% (Chinh et al., 2016; Cruijssen, Bräysy, et al., 2007; Ergun et al., 2007; Muñoz-Villamizar et al., 2015). In the case of each customer requiring service by two or more carriers Fernández et al. (2018) obtained cost savings of 6% −25%. Next to the economical aspect, the nature of collaboration between carriers signifies a reduced negative impact on the environment. These aspects are found in the research by Ballot and Fontane (2010), Muñoz-Villamizar et al. (2015), Pérez-Bernabeu et al. (2015), and Schulte et al. (2017) which study the reduction of routes and vehicles leading to a decrease in CO2 emissions and congestion in cities. From the numerical solving perspective, collaborative VRPs encompass a great complexity which requires the use of heuristic and metaheuristic approaches. With regard to the VRP, the solving mechanisms are found in Cordeau et al. (1997,2007), Laporte (1992), and Tarantilis (2005). Collaborative VRPs solving algorithms are discussed by Defryn, Sörensen, and Cornelissens (2016), Pérez-Bernabeu et al. (2015), and Sanchez et al. (2016). 2.2. Cost allocation methods In the scenario of collaboration, the profits gained by the coalition and the costs assumed have to be shared among the participants. A transparent and fair mechanism to split these values is necessary in order to assure the collaborative relationships between the partners and their long-term participation (Defryn, Sörensen, & Cornelissens, 2016). In the context of the VRP and its variations, the cost allocation problem consists of splitting the cost of the route/s between the customers served. This was first addressed by Göthe-Lundgren et al. (1996). Some other practical applications were developed by Engevall et al. (2004), Krajewska and Kopfer (2006), and Krajewska et al. (2008). For CVRPTW, cost allocation was first studied by Cruijssen et al. (2010) and later analyzed by Dahl and Derigs (2011) in a dynamic setting. In their survey, Guajardo and Rönnqvist (2016) show that in most cases in literature cooperative game theory is applied for the sharing of costs or profits. The authors categorize more than 40 methods either as traditional or ad-hoc. The first one refers to methods arising from previous work on cooperative game theory whereas ad-hoc are methods which result out of the particular conditions of the problem. Nonetheless, they conclude that a big majority of the methods found in literature fall into the following: • the Shapley value (Shapley, 1953), generally the most applied method which we explain later; F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681244 • proportional methods, where the cost is divided proportionally to a variable to each carrier (e.g. carrier j is allocated cost αj). The share of cost assigned to each player can follow different criteria (e.g. shared equally among players, according to their demand quantities or standalone costs); • the nucleolus method (Schmeidler, 1969), which looks for an individually rational distribution in which the maximum dissatisfaction is minimized. Table 1extracted from the literature survey by Guajardo and Rönnqvist (2016) summarizes the methods that are of most relevance for our work. From the traditional methods, the Shapley value is the one we focus on given its broad use. The methods consolidated under the category "ad-hoc" respond to those following definitions which concern the particular context where the research has been motivated, including modifications of traditional methods. In their work Shi et al. (2020) analyse the problem of sharing profits in collaborative vehicle routing problems with multiple depots. A similar approach is what we apply for splitting costs in problems with rather one depot and the added constraint of time-windows. Akkerman and Mes (2022) analyze how customer selection in vehicle routing problems could be approximated by the distance. We expand this area of study by addressing which other features, and to which extent, could be used to approximate cost being allocated to customers. To our best knowledge, there is no academic work where the cost allocation for collaborative environments of CVRPTW is addressed through approximation methods using linear regression. This is what we wish to explore with our work. 3. Methodology As the focus of this work is to analyze the applicability of direct rules and approximate a formula for the cost allocation of clients in a collaborative vehicle routing problem, we will develop our work by evaluating different CVRPTW Solomon data instances (Solomon, 1987) and assessing how the measures designed fit the outcome obtained. Firstly, we model the logistics problem as a vehicle routing problem with the added constraints of vehicle capacity and time windows and build our optimization model. In order to streamline the computation of our results, a metaheuristic solver is introduced. Further, we assess different methods for the allocation of costs in collaborative games. In particular, the full calculation of the Shapley value is initially adopted and later replaced with a structured random sample-based method. Finally, our model is applied to existing problem instances so as to derive the results which are later analyzed. 3.1. Modelling and solving of vehicle routing problems 3.1.1. Capacitated Vehicle Routing Problem (CVRP) For the modelling of our problem, we start with a simpler case in the CVRP. In this regard, the two-index flow formulation by Toth and Vigo (2014) is used. The CVRP aims at finding the set of routes that allow all customers’ demands in a network to be serviced by a fleet of vehicles starting from a depot with the minimum cost. Further, customers’ demands and geographical locations are deterministic with the latter deriving in the network of possible arcs available between nodes. Vehicles have a limit to the capacity that they can carry. In this regard, the notation is defined in the following. Let V=0,..., nbe the vertex set, where vertices i=1,..., ncorrespond to the customers and vertex 0 corresponds to the depot. Ais then the arc set which completes the graph G= (V,A), with each arc having a cost ci j associated with it: (i,j)∈A. Furthermore, each customer has a demand dito be fulfilled by a set of Kavailable vehicles (Kbeing not smaller than the minimum amount of vehicles needed to serve all customers), which are indistinguishable with the same capacity Cmeasured in the same units as the demand. For a given circuit, the cumulative demand of all the customers served by it must not exceed the vehicle capacity. Finally, given a subset S⊆V\{0}, we denote by r(S)the minimum number of vehicles needed to serve all customers in S. In all the instances we use throughout our work, vertices are defined by points with specific coordinates. Further, the cost ci j linked to each arc (i,j)∈A, is calculated as the Euclidean distance between the two points corresponding to the vertices iand j. This results in a cost matrix which is symmetric and satisfies the triangle inequality: cik +ck j ≥ci j ∀i,j,k∈V which signifies that any deviation from the direct link between two vertices results in a bigger distance, therefore bigger cost. In the remaining of this work, distance will be used as a measure of cost and vice-versa. The model uses binary variables xi j which take the value of 1 if the arc (i,j)is traversed in the solution and 0 otherwise. With the notation described, the problem formulation is as follows: minX i∈VX j∈V ci j xi j (1a) s.t.: X i∈V xi j =1∀j∈V\{0}, (1b) X j∈V xi j =1∀i∈V\{0}, (1c) X i∈V xi0=K, (1d) X j∈V x0j=K, (1e) X i/∈SX j∈S xi j ≥r(S)∀S⊆V\{0},S=;, (1f) xi j ∈ {0,1} ∀i,j∈V. (1g) The objective function in equation 1a aims at minimizing the sum of costs deriving from traversing the routes. Constraints 1b and 1c ensure that each customer is visited only F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1245 Table 1: Cost allocation methods in a collaborative environment found in academic literature (Guajardo & Rönnqvist, 2016). Method No. of articles References Ad hoc 31 (Agarwal & Ergun, 2010; Anily & Haviv, 2007; Audy et al., 2011,2012; Caprara & Letchford, 2010; Cheng et al., 2013; Dahl & Derigs, 2011; Dai & Chen, 2012,2015; Derks & Kuipers, 1997; Engevall et al., 1998,2004; Estévez-Fernández et al., 2009; Faigle et al., 1998; Fiestras-Janeiro et al., 2013; Fiestras-Janeiro et al., 2012; Flisberg et al., 2015; Frisk et al., 2010; Guajardo & Rönnqvist, 2015; Hamers et al., 1999; Hezarkhani et al., 2016; Liu et al., 2010; Özener, 2014; Özener & Ergun, 2008; Özener et al., 2013; Potters et al., 1992; Sun et al., 2015; Toriello & Uhan, 2013; Vanovermeire & Sörensen, 2014b; Yang et al., 2016; Yilmaz & Savasaneril, 2012) Shapley 23 (Agarwal & Ergun, 2010; Cheng et al., 2013; Cruijssen et al., 2010; Dror, 1990; Engevall et al., 1998,2004; Fang & Cho, 2014; Fiestras-Janeiro et al., 2012; Frisk et al., 2010; Guajardo et al., 2016; Hezarkhani et al., 2016; Krajewska et al., 2008; Liu et al., 2010; Lozano et al., 2013; Massol & Tchung-Ming, 2010; Özener et al., 2013; Sun et al., 2015; Vanovermeire & Sörensen, 2014a; Vanovermeire et al., 2014; Wang et al., 2015; Wong et al., 2007; Yengin, 2012; Zakharov & Shchegryaev, 2015) Proportional 18 (Audy et al., 2012; Berger & Bierwirth, 2010; Dror, 1990; Engevall et al., 2004; Fishburn & Pollak, 1983; Flisberg et al., 2015; Frisk et al., 2010; Hezarkhani et al., 2016; Krajewska & Kopfer, 2006; Lehoux et al., 2011; Liu et al., 2010; Massol & Tchung-Ming, 2010; Nguyen et al., 2014; Özener, 2014; Özener & Ergun, 2008; Özener et al., 2013; Sun et al., 2015; Wong et al., 2007) once allowing for exactly one arc to enter and leave each vertex associated with them. Consequently, constraints 1d and 1e impose analog requirements to the depot. Note that with this notation the CVRP aims at finding a collection of exactly K circuits to serve all customers, where each circuit starts and ends at the depot. Constraints 1f ensure connectivity of the paths in the solution while also imposing the vehicle capacity requirements. The constraints remain valid also if r(S)is replaced by a trivial lower bound defined by ⌈d(S)/C⌉(Cornuejols & Harche, 1993) with d(S) = Pi∈Sdidenoting the total demand of the set S⊆V. Lastly, constraint 1g represents the binary constraint. The family of constraints 1f has a cardinality which grows exponentially with n(Toth & Vigo, 2014). A family of equivalent constraints with polynomial cardinality can be used by utilizing the sub-tour elimination constraint of the Travelling Salesman Problem (TSP) applied to the CVRP (Christofides, 1979; Desrochers & Laporte, 1991; Miller et al., 1960): ui−uj+C xi j ≤C−dj∀i,j∈V\{0},i=j(2a) such that di+dj≤C, di≤ui≤C∀i∈V\{0}, (2b) where the variable ui,i∈V\{0}is added to the model, accounting for the load of the vehicle after visiting customer i. With this definition, when xi j =0, constraint 2a is not binding, while when xi j =1 then uj≥ui+djimposing the capacity and connectivity requirements and eliminating isolated sub-tours in the process (Toth & Vigo, 2014). 3.1.2. CVRP with Time Windows (CVRPTW) The CVRP with Time Windows extends the CVRP further restricting the problem by adding a time dimension. Each customer is associated with a time interval in which it needs to be served, called a time window. Further, the travel time, ti j, for each arc (i,j)∈Ais known and normally taken as the same as the distance or cost of the arc ci j. Additionally, service times siare given for each customer iand the time instant in which the vehicles leave the depot is also known and normally assumed to be at 0. As a result, the service at each customer ihas to be initiated during their time window and it lasts the service time associated with it si. Furthermore, whenever a vehicle arrives earlier than the start of a customer’s time window, it is allowed to wait until it begins and then commence service. For the purpose of this work and to summarize it’s main characteristics, the classical CVRPTW consists of defining exactly one circuit per vehicle (of the total Kvehicles available) minimizing the cost with: • each vehicle starting and finishing at the depot, • customers being serviced exactly once, • the capacity of the vehicles Cnot exceeding the sum of the demands of the customers serviced by it, • service starting within the time window [ai,bi]of each customer and the vehicle remaining a time equal to si at location i. The model used in our work for the CVRPTW follows the formulation by Toth and Vigo (2014), which is here described. It is based on the three-index vehicle flow model which allows for the modelling of more constrained versions of the vehicle routing problem, due to being more flexible in integrating additional dimensions. F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681246 Firstly, a network G= (V,A)is defined by the set of vertices of customers and the depot, which in this case is represented by the two nodes 0 and n+1. The set of customers N is then defined as all vertices but vertices 0 and n+1, namely N=V\{0,n+1}. Further, for a route to be feasible then it must start from node 0 and end at node n+1. Additionally, a time window [ai,bi]is associated with each customer i. Nodes 0 and n+1 are assigned Eand Las their earliest possible departure and the latest possible arrival at the depot respectively; that is, [a0,b0] = [an+1,bn+1] = [E,L]. Moreover, and in accordance with the problem description, zero demands and service times are defined for these two nodes, namely d0=dn+1=s0=sn+1=0. Let ∆+(i)denote the set of vertices jthat are connected to the vertex idirectly, such that arc (i,j)∈A. In the same manner, ∆−(i)denote the vertices from which iis directly reached, e.g. the set of vertices jsuch that arc (j,i)∈A. For each arc (i,j)∈Aand vehicle k∈K, a variable xi jk is introduced which takes the value of 1 if arc (i,j)is used by vehicle kand 0 otherwise. Further, a time variable wik is added for all nodes i∈Vand vehicles k∈Kwhich designates the time of the start of service at node iby vehicle k. With the described notation, the formulation as of Toth and Vigo (2014) is as follows: minX k∈KX (i,j)∈A ci j xi jk (3a) s.t.: X k∈KX j∈∆+(i) xi jk =1∀i∈N, (3b) X j∈∆+(0) x0jk =1∀k∈K, (3c) X i∈∆−(j) xi jk −X i∈∆+(j) xjik =0∀k∈K,j∈N, (3d) X i∈∆−(n+1) xi,n+1,k=1∀k∈K, (3e) xi jk wik +si+ti j −wjk≤0∀k∈K,(i,j)∈A, (3f) aiX j∈∆+(i) xi jk ≤wik ≤biX j∈∆+(i) xi jk ∀k∈K,i∈N, (3g) E≤wik ≤L∀k∈K,i∈ {0, n+1}, (3h) X i∈N diX j∈∆+(i) xi jk ≤C∀k∈K, (3i) xi jk ∈ {0,1} ∀k∈K,(i,j)∈A. (3j) The objective function calculates the total cost incurred which we aim to minimize. Constraints 3b ensure that each customer is assigned to exactly one route. Further, constraints 3c to 3e designate the flow on the path to be followed by vehicle k. After, constraints 3f to 3h ensure the time schedule is feasible while 3i guarantees the capacity constraint. Finally, constraints 3j ensure the binary conditions of the variables xi jk. 3.1.3. Metaheuristic solver The CVRP, as described in Section 3.1.1, is a generalization of the TSP (this being a CVRP with one vehicle visiting all vertices in a cost-minimizing circuit with C≥d(V)and K=1). This problem and its extensions with Time Windows (CVRPTW) is known to be strongly NP-hard (Toth & Vigo, 2014). For this reason, it would be very expensive computationally to solve each problem to optimality. As a consequence, a solver algorithm using metaheuristics is implemented. VROOM is an open-source optimization engine specifically tailored for VRPs which provides very good solutions in little time (VROOM Project, 2022). As an example of it performance, Table 2shows the results obtained when solving Solomon 56 instances of 100 customers which are used for benchmarking. By comparing the cumulated traveled time, it is observed that the maximum gap difference with the bestknown solution is 3.89%, all with an average computing time of 359 milliseconds. The mentioned algorithm utilizes different heuristics depending on the problem to find an initial solution. In the case of the CVRPTW, it uses modified versions of Solomon insertion heuristics. To improve the solution, a local search procedure consisting of 14 different operators is then performed to check for better feasible neighboring solutions (Bräysy & Gendreau, 2005). In their work comparing tools for solving CVRPTW, Puka et al. (2019) find that VROOM in comparison with other open-source solvers is one of the most balanced in terms of solution quality and execution time. For all the aforementioned reasons, it is used in our research. 3.2. Cost allocation in VRPs in a collaborative environment In this section, the vehicle routing problems previously defined are introduced in a collaborative environment in which several companies, each with a set of customers to serve, form a coalition that aims at satisfying the demand of all customers in a joint operation. In this setup, all customers and their demands are joined into a holistic logistic problem that is indifferent to the source of each customer. Operating as a joint venture, it has been shown that a total reduced cost is achieved while serving all customers. This is produced by the increased efficiency in the joint logistic operation due to customers with similar locations or service time windows being visited by the same vehicle. The cost that companies pay for such an optimization coalition is having to share their customer information which may be of high value for their business. We will consider a set of partners which form a grand coalition sharing their resources (vehicles) and demands. An example of such a collaborative CVRP is displayed in Figure 1where 3 partners join in a coalition to serve all of their customers resulting in a completely different total logistic operation. When working as a coalition of two or more partners, the problem arises of distributing the costs (or the profits) of serving the customers as a whole. In this regard, a mechanism is needed to allow for each customer that is brought F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1247 Table 2: Comparison to best known solutions (BKS) targeting cumulated travel time (CTT). Cumulated number of vehicles (CNV) is only reported for the record. (VROOM Project, 2022) Class C1 C2 R1 R2 RC1 RC2 Total BKS CNV 10.0 3.0 13.25 5.36 12.88 6.25 485 BKS CTT 828.38 589.86 1175.75 878.41 1340.02 1004.21 54699 VROOM CNV 10.0 3.0 13.25 4.27 13.25 5.25 468 VROOM CTT 828.38 589.86 1191.99 912.60 1356.76 1030.75 55,616 CTT gap +0.00% +0.00% +1.38% +3.89% +1.25% +2.64% +1.68 Figure 1: Example of a collaborative VRP where 3 partners (top green, cyan, blue) work jointly on a logistic operation. in the coalition by a partner to be correctly accounted for the marginal cost it produced to the total operation. Despite no method being considered as a global best practice, Defryn, Vanovermeire, and Sörensen (2016) argue that a cost allocation method based on the incentives of each partner should be selected by the coalition. This results in the group behaving in the best interest of the whole, e.g.: a cost allocation based on volume will derive in benefit for those who transport the highest volumes therefore steering the coalition into increasing the total volume displaced. Nonetheless, there is a general consensus on the fact that incentive criteria results in a fair distribution of costs in all cases (Defryn, Sörensen, & Cornelissens, 2016). We follow with the introduction of the concepts behind cooperative game theory and an axiombased cost allocation method: the Shapley value. 3.2.1. Cooperative game theory: Core In game theory when evaluating a game, one is interested in knowing the value each player adds to a coalition when a group of players cooperates and obtains a certain overall gain from that cooperation. Some players’ contributions may be larger or they may have a bigger bargaining power, even so to the extent of threatening to destroy the entire surplus. Therefore, the goal of this assessment would be to determine how important is each participant to the overall coalition, and what would therefore be their expected fair payoff. An analogous formulation applies to the case of determining the F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681248 cost of each customer added to a collaborative logistic problem as the only adjustment is that in the VRP each added player (customer) to the coalition will add a cost for the total operation instead of a surplus. Let us introduce some cooperative game theory concepts as described by Guajardo and Rönnqvist (2015). For a cooperative game in which the "grand coalition" of all players in the set N={1,...,n}participate, there is a characteristic function vwhich assigns a total cost for each coalition S∈Pwith Pcomprising the set of all possible subsets of N. In our case, this cost is calculated by solving the corresponding optimization problem of the CVRPTW for the coalition Sof customers (players). A cost allocation vector z=z1,...,zj,...,znis such that allocates a cost for each player j∈Nsuch that: X j∈N zj=v(N). The equation above represents the "efficiency" condition in which the total cost of the grand coalition is split among its members according to z. Moreover, the "rationality" condition states that the sum of the allocated costs to each player of a coalition should be no bigger than the total cost of the coalition; e.g. no subset Sof players can be formed where the cost resulting from a coalition with all of them is smaller than the total cost allocated to them according to z, namely: X j∈S zj≤v(S)∀S∈P. In the context of a CVRPTW, a rational cost allocation vector would be one that allocates the cost to each customer such that no combination of customers can yield a smaller cost when served than the sum of their allocated values. The "individually rational condition" is a particular case for coalitions Sof only one player, in which the cost allocated to it should not be bigger than its stand-alone cost: zj≤v({j}). If a customer were to be assigned a cost bigger than its standalone cost it would not make any sense for the carriers to bring them into the pool of shared customers. Most importantly, as defined by game theory, the core in a cooperative game is the set of allocation vectors that satisfy the condition of rationality; that is: Core(v) = (z∈Rn:X j∈N zj=v(N),X j∈S zj≤v(S)∀S∈P). When an allocation vector is included in the core, it is said to provide "stability", given that there is no reason for players in the grand coalition to form a smaller coalition as this yields a worse outcome. The core is widely utilized as a measure of stability in research (Guajardo & Rönnqvist, 2016). 3.2.2. Shapley value allocation method An answer to the profit(cost) allocation issue in cooperative games was introduced by Lloyd S. Shapley (Shapley, 1951,1953). It distributes the total gains of the contributor players, assuming a non-zero contribution by all members of the coalition. The Shapley value is then calculated by accounting for all the possible orders a contributor may arrive to the coalition and computing each of their marginal contributions and average it over the total. It is based on a set of axioms which define the main characteristics a solution to the cost allocation problem should fulfill (Defryn, Sörensen, & Cornelissens, 2016). These axioms are the following: • Symmetry: Interchangeable agents(customers) should receive the same share of the cost. • Null player property: An agent who neither adds nor reduces the cost of any coalition should be allocated no cost. • Efficiency: The sum of all costs allocated among all the agents should total the total coalition cost. • Additivity: The sum of the cost allocated to agents a and b should be the same as that allocated to a third partner representing them. • Individual rationality: The cost allocated to an agent cannot be larger than its stand-alone cost. The allocation through the Shapley value to each player ican be calculated using 4where the final term is the computation of the marginal contribution of player ito a certain sub-coalition S, being v(S)the characteristic function which describes the worth of coalition S, e.g.: the total expected payoff Scan obtain by cooperation. These marginal costs are calculated for each possible sub-coalition and then averaged by the weight that each possible combination of such sub-coalition may be reached. φi(N,v) = 1 N!X S⊆N\{i} |S|!(|N|−|S|−1)![v(S∪{i})−v(S)] (4) The following simple example depicts the calculation of the Shapley value. Suppose there are three players {1,2,3} participating in a collaborative game with each of the possible sub-coalition resulting in the payoffs summarized in Table 3. Further, as we add players to the coalition in each of the 6 ways the grand coalition could be formed, each player in turn is going to add a marginal contribution as displayed in Table 4. Therefore, the expected marginal contribution and Shapley value for each player is simply the average value of these contributions. In our scenario, we use the Shapley value to compute the cost each customer contributes to the total cost of serving them all together. That is, each customer is a player and we calculate the costs resulting from the objective function of the VRP for all the possible customer combinations. Although the Shapley value defines a fair way of dividing the grand coalition’s payment among its members, its result does not guarantee stability. This means some players might be better off when forming a different coalition than the grand coalition. However, the existence of a stable cost F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1255 Figure 6: Solution to Solomon’s instance R201.50 showing the computed cost (Shapley value) for each customer. Figure 7: Example of computing the proximity customers for a customer i. Further, as in the case of the distance between customers, the spread in the time windows is looked to be reflected in the time window overlap as defined in the time feature: TFi 2=∥{j∈J}∥ :(ai,bi)∩aj,bj=; Instance-specific features Relying on the characteristics of Solomon instances which aim at characterizing the different dimensions affecting CVRPTW, we use certain instance-specific features which aid in the analysis of the costs and their distributions between instances themselves. For this purpose we separate instances under the following classification: • Customers proximity: Clustered/Non-clustered customers • Time: Tight/Non-tight Time Windows Additionally, different modelled instances are compared using other characteristics which are not binary to the extent that they are not directly related to the Solomon instances’ design criteria such as: • Average customer demand F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681256 • Ratio of total demand served by vehicle capacity • Average length of time windows • Average number of customers per tour 5. Analysis and discussion With the data generated for the instances used and the features calculated we follow with the statistical analysis in the following sections. 5.1. Results obtained and observations The results obtained from applying our methodology are compiled in Appendix 1 where the characteristics of each node from Solomon instances in conjunction with the cost assigned in the grand coalition are shown. As in Section 4.1, we begin by addressing the total savings of each carrier when collaborating which are summarized in Table 10 where the average value has been added for further study. We can again observe that all gains are positive, in line with the research findings explained in Section 2.1, and further enlarging the case for collaboration between carriers. Worth noting is that this is the total gains for each carrier (each of which has a similar share of assigned customers), which does not exclude the possibility of a customer bringing a negative gain when shared into the common pool of the joint operation. This is later explored in Section 5.4. We can therefore observe the following: Observation 1. The total savings calculated for each individual carrier when collaborating in a grand coalition are found to be positive in all instances. Within this level of granularity, we want to evaluate the differences in the costs allocated and the corresponding savings obtained for the customers in each instance. Figure 8 depicts the average values obtained in instances split by clustering and the time window horizon. In Figure 8a we observe that the clustering of customers yields a smaller average cost per customer. Further, Figure 8b shows how having short time windows affect considerably the average cost of serving the customers. Interestingly, in both cases the savings do not show the same level of change. To further study the instance-related features, Figure 9 compiles the same measures for average cost and savings compared to the different characteristics of the Solomon instances. Firstly, an increase in the average customer demand leads to an increase in the savings as shown in Figure 9a. Moreover, when analysing Figure 9b we observe no general trend for lower demands per truck capacity but notice an increase in the savings and costs when increasing past a certain threshold. We can relate the results from Figure 8b with Figure 9c where we observe that a decrease in the average time window length results in a smaller average cost allocated to each customer. Finally, with regard to the average number of customers per tour, Figure 9d shows that average costs decrease when this increases. Throughout the results showed, a clear relation between costs and savings can be observed, pointing towards the fact that the same limitations that increase the cost of serving the pool of customers are the ones that can be avoided when collaborating. Let us summarize the main observations in the following: Observation 2. Customer clustering and relaxation of time windows yield a decrease in the average cost of serving each customer. Observation 3. An increase in customer demand or a decrease in the vehicles’ capacity leads to an increase in the costs associated with each customer. Observation 4. As the total amount of tours to serve a certain amount of customers decreases, the average cost associated with each customer also does. Observation 5. There is a strong correlation between the costs assigned to each customer when serving them in a stand-alone operation and the potential savings when acting in a collaborative environment. Although always dealing with a collaborative scenario, the cost allocation deriving from the joint operation can be analyzed from a non-collaborative perspective. The grand coalition acts as a shared resources all-information central planning body. For the approximation of the cost allocation with the features defined, we start with the results obtained from the centrally planned cost allocation perspective. Later, we analyze the data resulting from expanding on the collaborative nature of the problem. 5.2. Model fit and feature selection Our main aim is to conduct a model selection procedure to choose the features and interactions of them which yield the best fit to the cost allocated to customers through linear regression. The measure used to compare the performance of different models is under debate, which questions the "best" fit (Hansen & Yu, 2001). Nevertheless, we will focus on the Akaike (AIC) and Bayesian Information Criterion (BIC) and the adjusted R2value as means of evaluating our models. Furthermore, for simplicity of our solution and following the principle of parsimony, or Occam’s razor, we will focus on finding the model with the least amount of features and interactions given similar explanatory power. To start, a multiple ordinary least squares linear regression analysis is conducted using all features in the model as the independent variables and the calculated allocated cost (Shapley value) as the dependent one. Said analysis is performed with the data for all the combined instances shown in Table 9. At first, we conduct our analysis without including an intercept in the model, with the results being presented in Figure 10. By applying a Breusch-Pagan test to the data, the null hypothesis of homoskedasticity is discarded therefore the regression results show the scores for t-tests using heteroskedasticity-robust standard errors. The model shows a high correlation with a value of R2of 0.855. Regarding the distance metrics, from the values of the regression coefficients, we can infer both a positive statistically significant F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1257 Table 10: Total savings for each carrier (A, B, C) in the modelled CVRPTW Solomon instances. Instance A B C Average C101.50 150.75 161.57 154.59 155.64 C201.50 135.59 113.51 156.80 135.30 R101.50 120.20 123.43 101.63 115.09 R201.50 145.82 131.90 128.99 135.57 RC101.50 228.59 152.04 166.80 182.48 RC201.50 263.92 251.12 228.17 247.74 C108.50 133.97 151.41 136.62 140.66 C208.50 127.60 102.38 137.47 122.49 R109.50 78.19 92.84 129.13 100.05 R209.50 112.12 124.45 136.17 124.25 RC108.50 219.75 204.91 202.62 209.09 RC208.50 210.48 213.47 204.14 209.36 Figure 8: Average costs and gains for the modelled Solomon instances split by clustering and TW horizon. Figure 9: Average costs and savings for the modelled Solomon instances in relation to different instance characteristics. F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681258 correlation between the cost and the relative distance to the depot (DF1) and a negative one with the amount of proximity points (DF2). This confirms the results previously discussed in Section 5.1 in Observation 2. With regard to the time features, the negative correlation of the relative time window length (TF1) signals a decrease in the cost when having less constraining time windows which also is in line with the previous observations. Further, a positive coefficient for the time window overlap (TF2) would be against the common sense of pricing time windows and will be explained through further analysis of different models. None of the capacity constraints appear to have any statistical significance given by the p-values of capacity-related features which we analyze later. To further explore the correlation between the variables let us analyze the relationship between each of them. Figure 11 shows a scatter plot for each of the variable pairs in the regression model. A grid of Axes is displayed such that each variable in the data will be shared across the yaxes across a single row and the x-axes across a single column. The diagonal plots show a distribution plot to represent the marginal distribution of each variable. Through an inspection of the scatter plots for the features in each dimension a clear correlation can be observed, in particular within distance-dependent and time-dependent features. This is further confirmed when calculating the correlation values as shown in Figure 12. As observed, the correlation between DF1 and DF2 is negative which means that having more points in the vicinity relates to a decrease in the distance to the depot or vice versa. Further, the correlation between features TF1 and TF2 is positive corresponding to a increase in the time window overlap when increasing the gap between the beginning and end of the allowed time for service at the customer. As observed in the relation between the features in each dimension, and due to over-redundancy, the results obtained signal the need of relying on one main factor for each of the dimensions specified (Capacity, Distance, Time). A model selection is then conducted to choose the best fit with the measures specified before. All the combinations of features are tested and their AIC, BIC and adjusted R2values are calculated. It is found that features DF1, TF1 and CF2 are the ones that yield a better explanation of the dependent variable remaining one of the relatively lowest models regarding the AIC and BIC scores. It is reasonable to believe that the inclusion of CF2 is related to the addition of the maximal vehicle capacity as a variable to the model. Further, of the proximity measures included for distance and time windows none remain as the selected by the model. As we see later, this is very much related to the degree customers are clustered and timeconstrained. The results for the regression with only these features are showcased in Table 11. The feature CF2 appears to have less statistical significance but has a negative coefficient which is in line with Observation 2. It is worth noting that the addition of an intercept in our model yields a lower explanatory effect over the independent variable given its R2 value but has a higher statistical significance for all the variables including the intercept and achieves a lower AIC and BIC value as displayed in the regression results in Figure 13. The addition of an intercept would signify a base cost allocated to customers in any case which would be a simple base pricing strategy from which to start. From the two linear regression models, with or without intercept, we can derive two main strategies to price customers. Firstly, one where no base price is defined and through the implementation of features pricing the dimensions which define each customer (demand, time window, distance) the final cost is greatly described. Secondly, assuming a basic price for all customers (intercept) and pricing the features differently resulting in reduced descriptive power of each feature on the final cost allocated to each customer. We will further study the pricing of the different features in the following section. As a whole, from all our regression models we can observe the following: Observation 6. The cost allocated to customers in vehicle routing problems with time windows can be estimated with a few defined features related to customers’ location, time window, demand and vehicle capacity. 5.3. Customer pricing The practical application of our work is focused on being able to price each of the characteristics that comprise the logistics problem of serving different customers whose geographical location, time demands and capacity vary. As defined in our cost-approximation function, the features introduced allow us to represent each of these dimensions in our model. None-withstanding, we want to study different ways of approaching these characteristics. As addressed in Section 4.2 the variety in the Solomon instances allow for the assessment of the results of our cost approximation when dealing both with clustered customers vs non-clustered ones and the time horizon restrictions. In this regard, we will study the differences in our regression models when dealing with each condition. 5.3.1. Clustered vs non-clustered customers For this comparison, instances with non-clustered customers which are located geographically in a random fashion (R101.50, R201.50, R109.50, R209.50) are compared with their clustered counterparts in which customers are in groups of close proximity to each other (C101.50, C201.50, C108.50, C208.50). Instances RC, being a mix of both, are left outside of the analysis. The results of the linear regression for both cases are compiled in Tables 12 and 13 where CF1 has been dropped for being highly correlated to CF2. The explanatory power of the models gives an adjusted R2 value of 0.624 for the clustered customers and 0.702 for the randomly located ones. It can be observed that for the nonclustered customers the intercept for the cost is not statistically relevant with only the relative distance to the warehouse being the relevant distance feature. In contrast, when dealing with instances of clustered customers, the intercept F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1259 Figure 10: Ordinate least squares regression results for all instances with all features in the model. Figure 11: Scatter plots of all the pairs of variables in the model. The variables’ distributions are shown in the diagonal plots. F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681260 Figure 12: Correlation values between each feature in the model. Table 11: Linear regression model summary with the cost (Shapley value) as the dependent variable and the selected features as independent variables. coef std err z P >|z|[0.025 0.975] DF1 14.933 0.492 30.380 0.000 13.970 15.897 TF1 -0.388 0.033 -11.893 0.000 -0.452 -0.324 CF2 -8.322 4.829 -1.723 0.085 -17.787 1.143 Figure 13: Regression results for the selected model features with an added intercept. becomes relevant in conjunction with the two distance-based features. In particular, the addition of DF2 which considers the proximity to other customers affects the cost negatively. Further, for the randomly located customers, the time features related to the length and overlap of time windows appear to be statistically significant and affect both the cost negatively. This would signify that time windows have a major impact on the cost of serving customers when these are not grouped in clusters of close proximity. Moreover, the difference in the coefficient for DF1 of more than 10 signifies a significantly bigger impact on the distances in the case of nonclustered customers compared to the clustered ones. All in all, our results clearly show how the grouping of customers in clusters can have a clear effect on the variables which mainly affect the allocation of costs. Further, having the geographical location as the only feature we would like to assess the pricing of certain regions or locations for our customers. In this regard, we compile all the customers from the instances mentioned above so as to show how distance to the depot, which translates into time in our model, affects cost allocation. Figure 15 shows the case of customers with random locations where zoning related to the distance to the warehouse is applied. In the case of clustered customers we summarize the customers of in- F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1261 Table 12: Linear regression results for the non-clustered customers. coef std err z P >|z|[0.025 0.975] const 10.011 5.494 1.822 0.068 -0.757 20.779 DF1 14.666 2.351 6.238 0.000 10.058 19.274 DF2 -0.282 0.206 -1.366 0.172 -0.687 0.123 CF2 -4.769 9.865 -0.483 0.629 -24.104 14.566 TF1 -0.328 0.076 -4.296 0.000 -0.477 -0.178 TF2 -0.121 0.030 -4.057 0.000 -0.180 -0.063 Table 13: Linear regression results for the clustered customers. coef std err z P >|z|[0.025 0.975] const 7.230 1.360 5.318 0.000 4.565 9.895 DF1 4.272 0.537 7.952 0.000 3.219 5.325 DF2 -0.215 0.036 -6.019 0.000 -0.285 -0.145 CF2 1.374 3.472 0.396 0.692 -5.431 8.179 TF1 -0.033 0.030 -1.121 0.262 -0.091 0.025 TF2 0.029 0.024 1.201 0.230 -0.018 0.077 stances RC101.50, RC201.50, RC108.50 and RC 208.50 in their respective clusters and then calculate an average cost per cluster which is represented in Figure 14. Both figures exemplify how different zoning rules can be applied to better adapt to the different structures of customer locations. 5.3.2. Tightness of time windows As in the case of distance, we proceed to analyze the effect of time in our problem by comparing instances which have a shorter time-horizon (e.g. R/C/RC 101.50) to those which a longer one (e.g. R/C/RC/201.50). For the case with tighter time restrictions, it can be observed that the significant features are only the relative distance to the depot (DF1) and both time features. The limitation that the time constraint produces, makes the overlap of time windows (TF2) a significant feature in contrast with the case with longer time horizons. Moreover, in the case with more relaxed time constraints the intercept becomes statistically significant yielding a basic cost as a base from which then the first distance measure and the relative length of the time windows both add and subtract respectively to the cost allocated for each customer. Further, the clustering of customers has a statistically significant correlation in this scenario as is the case with the capacity. In general, we observe that short scheduling horizons, allowing for only a few customers to be serviced per route, yield a higher variance of the cost allocated to each customer. To summarize, the individual regression models of each of the different set of instances has shown how the pricing strategy of customers depends greatly on the configuration of them. It can be derived that the classification of customer configurations among the categories used results in a better understanding of how to divide the costs when serving them. 5.4. Collaborative gains analysis One of the main areas of focus of our work is the cooperation aspect of the logistics carriers in this problem. Given that we are dealing with a collaborative scenario, we are interested in evaluating the allocation of costs of each carrier when operating individually compared to that when in cooperation. So far, we have allocated costs based on a joint logistic operation in which we have assumed that all carriers share their entire pool of customers and vehicle resources so as to achieve the most efficient service from a logistics perspective. There is however a reluctance of carriers to share all their customers’ information given that this is from where their business extracts great value. As explained, for each of the instances modelled we have assigned each customer in the pool to one of three carriers. We therefore utilize our methodology within each carrier’s operation solving the CVRPTW and using structured random sampling to calculate the Shapley value and allocate the cost of each customer in a partner stand-alone operation. These results can be found in Appendix 1 under the carrier’s assignment and the stand-alone cost. Moreover, for each of the customers of the competitors, a cost is calculated considering what would be the cost allocated to that customer if the entire operation was to be delivered to an identical pool of customers with the only addition of this extra one. This is represented in Figure 16. In this scenario, the mechanism of an auction is being reproduced where a carrier would offer a customer to the pool of shared customers. In 5.9a carrier 1 would offer a customer for which it has a high cost allocated. Secondly, in 5.9b the other carriers calculate their cost when adding this customer to their service. Finally, the carrier with the lowest servicing cost wins the auction given that he can pay a higher price because he can include the customer with the lower marginal cost. This results in the transfer of this customer from one operator to the other. Considering this, we calculate for each F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681262 Figure 14: Cost assigned for each customer cluster in clustered instances. Figure 15: Distribution of cost for customers in instances with randomly chosen locations. Table 14: Linear regression results for the instances with a shorter time horizon. coef std err z P >|z|[0.025 0.975] const 5.490 3.071 1.788 0.074 -0.529 11.508 DF1 16.134 2.187 7.378 0.000 11.847 20.420 DF2 0.029 0.087 0.335 0.737 -0.141 0.200 CF2 -16.001 8.931 -1.792 0.073 -33.505 1.504 TF1 -5.495 0.566 -9.712 0.000 -6.604 -4.386 TF2 0.126 0.057 2.191 0.028 0.013 0.239 carrier the Shapley value for each customer of the competitors. The lowest cost from the computation of other carriers’ operations is presented in the last column in the table found in Appendix 1. Our calculations are not completely representative of the entire auctioning process because they only consider the first iteration of it. This proves to be sufficient for our analysis. We follow with the analysis of two scenarios. In the first F. Arroyo /Junior Management Science 9(1) (2024) 1241-1268 1263 Table 15: Linear regression results for the instances with a longer time horizon. coef std err z P >|z|[0.025 0.975] const 17.964 2.938 6.115 0.000 12.207 23.722 DF1 7.918 1.593 4.969 0.000 4.795 11.041 DF2 -0.402 0.067 -5.972 0.000 -0.533 -0.270 CF2 -98.750 35.031 -2.819 0.005 -167.410 -30.091 TF1 -1.096 0.418 -2.622 0.009 -1.915 -0.277 TF2 -0.042 0.090 -0.470 0.638 -0.219 0.134 Figure 16: Representation of an auction mechanism for the sharing of customers in a collaborative vehicle routing problem. one, we compare the stand-alone operation of each carrier with the grand coalition (central plan) where all customers are shared. For the second scenario, we consider the aforementioned auction mechanism in which we compare the cost of every customer in each carriers’ operation to that of their competitors. 5.4.1. Central plan comparison The aim is to derive insights into which customers become detrimental when being shared which defeats the purpose of sharing the information in the search of reducing costs. Accordingly, we calculate customers’ Shapley value in carriers’ stand-alone operation and in a grand coalition. We then classify customers who yield a negative/positive gaining so as to perform a logistic regression with the variables in the data. A dummy variable is used with a value of 1 for customers with a positive gain when shared and 0 otherwise. The aim is to have a prediction of which customers should be shared and which should be kept. Consistently with the rest of our work, the instances mentioned in Section 4.2 are used. Of the 600 customers, 33 yield a negative gain. From our statistical analysis, only the relative distance yields any statistical significance in the explanation of the dependent variable. The results for the regression when using only this feature are condensed in Figure 17. Further, the gains for each customer when cooperating are also regressed with the features constructed so far. The results are showcased in Table 16 where the effect of both distance features are found to have a significant correlation. Apart from the significant descriptive value of the distance features, there is no particular difference found for the 33 customers for which gains are negative. This constitutes a paradox, given that the cost for these customers is higher in the collaborative scenario than when in a partner stand-alone undertaking, but still carriers benefit from the collaboration as a whole when summing all customers. There is, therefore, a contradiction between the cost-allocating problem and the logistics problem which represents an area of potential future work. In general, we found a very strong correlation between the costs allocated to customers when carriers act alone and those when doing so in a collaborative scenario. Figure 18 shows this relationship which yields a high value of R2, confirming Observation 5. 5.4.2. Auction scenario Analogously, the same procedure from the central plan scenario is applied to the auction one. Of the 600 customers F. Arroyo /Junior Management Science 9(1) (2024) 1241-12681264 Figure 17: Logistic regression result when predicting a customer’s gain in collaboration. Table 16: Linear regression results for the gains obtained for each customers when carriers collaborate. coef std err z P >|z|[0.025 0.975] const 8.258 1.988 4.153 0.000 4.361 12.155 DF1 6.570 1.153 5.700 0.000 4.311 8.830 DF2 -0.370 0.062 -5.931 0.000 -0.492 -0.247 CF2 11.034 9.540 1.157 0.247 -7.664 29.732 TF1 0.044 0.043 1.017 0.309 -0.040 0.127 TF2 -0.007 0.021 -0.328 0.743 -0.047 0.034 Figure 18: Correlation between savings in collaboration and costs in stand-alone allocated to customers. studied, 167 yield a negative gain when comparing it to the lowest servicing cost from other carriers; that is, only 167 customers are serviced with the lowest cost by the carrier they have been assigned to. We follow with the same logistic regression as with the case before which only has a significant correlation with DF1 with a coefficient of 0.90. Moreover, a linear regression model is constructed with the defined features as independent variables and the gains by auctioning as the dependent one. The results from the OLS regression is shown in Table 17. Although having a low explanatory power with an adjusted R2value of 0.069 , the intercept has a significant statistical value. Noticeably, the only other feature with statistical significance is DF2 measuring the degree of clustering of customers. This represents that customers which are closer to other customers yield a lower cost for other carriers than the one serving them. Given the outcome observed for this scenario, it is sensible to expect all total savings of carriers when collaborating to be positive, as our results in Section 5.1. This is explained in the fact that the great majority of customers can be serviced with lesser cost by a different carrier than the one to which they have been assigned. In practical scenarios, decentral collaboration can be exercised for the sharing of selective customers which are found to bring the biggest cost. In our results, we find that the average cost allocated in a standalone operation to customers that are cheaper to service by other carriers is 23.84 compared to 15.32 for those which are not. This represents a significant difference of 56% bigger cost.