•We introduce the minimum cost network design problem in strategic alliances.•We consider transaction costs induced by the formation of the alliance.•We concentrate on bilateral alliances.•Accounting ...for the transaction cost in network design is vital for the alliance.•These transaction costs may even render the collaboration unattractive.
Strategic alliances are established between firms to improve their competitiveness in markets and generally appear in the form of joint ventures. Such collaborative efforts require centralized planning, and the survival of the alliance largely depends on the success of joint planning processes. In this regard, we investigate the opportunities that centralized collaboration can offer to firms when designing their service networks. Apart from the classical fixed and variable costs associated with the network design, we also consider transaction costs induced by the formation of the alliance, which can broadly be defined as cost components related to the coordination and monitoring of the people, efforts and resources. We concentrate on bilateral alliances and develop alternative models for solving their associated network design problem. We also adopt a state-of-the-art heuristic to solve large-scale instances. Our findings confirm that accounting for the transaction cost in network design is vital for the alliance. These transaction costs can be high enough to even render the collaboration unattractive. Hence, careful data collection and model treatment are required before deciding whether to form an alliance.
In order to foster electric vehicle (EV) adoption rates, the availability of a pervasive and efficient charging network is a crucial requirement. In this paper, we provide a decision support tool for ...helping policymakers to locate and size EV charging stations. We consider a multi-year planning horizon, taking into account different charging technologies and different time periods (day and night). Accounting for these features, we propose an optimization model that minimizes total investment costs while ensuring a predetermined adequate level of demand coverage. In particular, the setup of charging stations is optimized every year, allowing for an increase in the number of chargers installed at charging stations set up in previous years. We have developed a tailored heuristic algorithm for the resulting problem. We validated our algorithm using case study instances based on the village of Gardone Val Trompia (Italy), the city of Barcelona (Spain), and the country of Luxembourg. Despite the variability in the sizes of the considered instances, our algorithm consistently provided high-quality results in short computational times, when compared to a commercial MILP solver. Produced solutions achieved optimality gaps within 7.5% in less than 90 s, often achieving computational times of less than 5 s.
A number of decision support tools facilitating the use of Electric Vehicles (EVs) have been recently developed. Due to the EVs’ limited autonomy, routing and path planning are the main challenges ...treated in such tools. Specifically, determining at which Charging Stations (CSs) to stop, and how much the EV should charge at them is complex. This complexity is further compounded by the fact that charging times depend on the CS technology, the EV characteristics, and follow a nonlinear function. Considering these factors, we propose a path-planning methodology for EVs with user preferences, where charging is performed at public CSs. To achieve this, we introduce the Electric Vehicle Shortest Path Problem with time windows and user preferences (EVSPPWP) and propose an efficient heuristic algorithm for it. Given an origin and a destination, the algorithm prioritizes CSs close to Points of Interest (POIs) that match user inputted preferences, and user-defined time windows are considered for activities such as lunch and spending the night at hotels. The algorithm produces flexible solutions by considering clusters of charging points (CPs) as separate CSs. Furthermore, the algorithm yields resilient paths by ensuring that recommended paths have a minimum number of CSs in their vicinity. The main contributions of our methodology are the following: modeling user-defined time windows, including user-defined weights for different POI categories, creating CSs based on clusters of CPs with sufficient proximity, using resilient paths, and proposing an efficient algorithm for solving the EVSPPWP. To facilitate the use of our methodology, the algorithm was integrated into a web interface. We demonstrate the use of the web interface, giving usage examples and comparing different settings.
•We describe electric vehicle batteries, their status and expected developments.•We outline battery lifetime degradation and instantaneous behaviour characteristics.•We provide tractable battery ...degradation and behaviour models.•We analyze the instantaneous charging and discharging behaviour of batteries.•We develop several insights of interest to scientists and managers.
The use of electric vehicles for goods distribution opens up a wide range of research problems. Battery electric vehicles (BEVs) operate on batteries that have a limited life, as well as specific charging and discharging patterns which need to be considered in the context of their use for goods distribution. While many transportation problems associated with the integration of freight electric vehicles in distribution management problems have been investigated, there is room for further research on specifically how to model battery degradation and behaviour in such problems. The aim of this paper is to provide tractable models for transportation scientists that will allow predicting the lifetime degradation and instantaneous charging and discharging behaviour of BEV batteries.
Stochastic vehicle routing, which deals with routing problems in which some of the key problem parameters are not known with certainty, has been an active, but fairly small research area for almost ...50 years. However, over the past 15 years we have witnessed a steady increase in the number of papers targeting stochastic versions of the vehicle routing problem (VRP). This increase may be explained by the larger amount of data available to better analyze and understand various stochastic phenomena at hand, coupled with methodological advances that have yielded solution tools capable of handling some of the computational challenges involved in such problems. In this paper, we first briefly sketch the state-of-the-art in stochastic vehicle routing by examining the main classes of stochastic VRPs (problems with stochastic demands, with stochastic customers, and with stochastic travel or service times), the modeling paradigms that have been used to formulate them, and existing exact and approximate solution methods that have been proposed to tackle them. We then identify and discuss two groups of critical issues and challenges that need to be addressed to advance research in this area. These revolve around the expression of stochastic phenomena and the development of new recourse strategies. Based on this discussion, we conclude the paper by proposing a number of promising research directions.
•We introduce and solve the electric vehicle routing problem with energy consumption uncertainty.•We formulate the problem as a robust mixed integer linear program.•We solve small instances to ...optimality using robust optimization techniques.•We develop a two-phase heuristic method based on large neighbourhood search to solve larger instances.•We perform an extensive computational study.
Compared with conventional freight vehicles, electric freight vehicles create less local pollution and are thus generally perceived as a more sustainable means of goods distribution. In urban areas, such vehicles must often perform the entirety of their delivery routes without recharging. However, their energy consumption is subject to a fair amount of uncertainty, which is due to exogenous factors such as the weather and road conditions, endogenous factors such as driver behaviour, and several energy consumption parameters that are difficult to measure precisely. Hence we propose a robust optimization framework to take into account these energy consumption uncertainties in the context of an electric vehicle routing problem. The objective is to determine minimum cost delivery routes capable of providing strong guarantees that a given vehicle will not run out of charge during its route. We formulate the problem as a robust mixed integer linear program and solve small instances to optimality using robust optimization techniques. Furthermore, we develop a two-phase heuristic method based on large neighbourhood search to solve larger instances of the problem, and we conduct several numerical tests to assess the quality of the methodology. The computational experiments illustrate the trade-off between cost and risk, and demonstrate the influence of several parameters on best found solutions. Furthermore, our heuristic identifies 42 new best solutions when tested on instances of the closely related robust capacitated vehicle routing problem.
We study a stochastic variant of the vehicle routing problem (VRP) arising in the context of domestic donor collection services. The problem we consider combines the following attributes. Customers ...requesting services are variable, in the sense that they are stochastic, but are not restricted to a predefined set. Furthermore, demand volumes are also stochastic and are observed upon visiting customers. The objective is to maximize the expected served demands while meeting vehicle capacity and time restrictions. We call this problem the VRP with a highly Variable Customer basis and Stochastic Demands (VRP-VCSD). We first propose a classical Markov Decision Process (MDP) formulation for the VRP-VCSD. The resulting model is, however, unusable due to the explosion in the dimension of the state and action spaces.
To solve the VRP-VCSD, we propose a number of methodological contributions aimed at reducing the state and action spaces. We first reformulate the MDP as an MDP with a consecutive action selection procedure. In this formulation, we enforce the treatment of a single vehicle (as opposed to multiple vehicles) at each decision epoch. We then introduce an observation function that selects a subset of the available information, which is deemed relevant for the considered vehicle in each epoch. We develop a Q-learning algorithm called QN-CO. In particular, we use a continuous state representation and incorporate a two-layer artificial neural network to approximate the Q values. Furthermore, we propose an aggregation strategy yielding a fixed-size output. Finally, we enhance our algorithm with Replay Memory and a Double Q Network.
We conduct a thorough computational analysis. Results show that QN-CO considerably outperforms five benchmark policies. Moreover, we show that QN-CO can compete with specialized methods developed for the particular case of the VRP-VCSD where customer locations and expected demands are known in advance.
•We introduced a VRP with stochastic customers and demands (VRP-VCSD).•We proposed a consecutive action selection procedure and an observation function to reduce the action and state spaces.•A Q-learning algorithm is adopted to solve the MDP formulations.•The proposed method outperforms five benchmark policies.
Since the mid-2000s, electric vehicles have gained popularity in several countries even though their market share is still relatively low. However, most gains have been made in the area of passenger ...vehicles and most technical and scientific studies have been devoted to this case. By contrast, the potential of electric vehicular technology for goods distribution has received less attention. The issues related to the use of electric vehicles for goods distribution reveal a wide range of relevant research problems. The aims of this survey paper are to provide transportation researchers an overview of the technological and marketing background needed to conduct research in this area, to present a survey of the existing research in this field, and to offer perspectives for future research.
Stochastic vehicle routing, which deals with routing problems in which some of the key problem parameters are not known with certainty, has been an active, but fairly small research area for almost ...50 years. However, over the past 15 years we have witnessed a steady increase in the number of papers targeting stochastic versions of the vehicle routing problem (VRP). This increase may be explained by the larger amount of data available to better analyze and understand various stochastic phenomena at hand, coupled with methodological advances that have yielded solution tools capable of handling some of the computational challenges involved in such problems.
In this paper, we first briefly sketch the state-of-the-art in stochastic vehicle routing by examining the main classes of stochastic VRPs (problems with stochastic demands, with stochastic customers, and with stochastic travel or service times), the modeling paradigms that have been used to formulate them, and existing exact and approximate solution methods that have been proposed to tackle them. We then identify and discuss two groups of critical issues and challenges that need to be addressed to advance research in this area. These revolve around the expression of stochastic phenomena and the development of new recourse strategies. Based on this discussion, we conclude the paper by proposing a number of promising research directions.