Search

Contracts in the for-hire trucking industry are unusual in that, although they establish prices for different services, there is typically no legally binding obligation or penalty for either party to offer or accept a load. When a load is rejected by all contract carriers, shippers must turn to the spot market, which can significantly increase supply chain costs. Because these transactions occur between private parties, data on load acceptances/rejections and contract/spot prices have not been available to academic researchers, leaving the freight rejection problem largely unexplored. We are able to examine this problem using a detailed transactional data set of a large national shipper. We estimate that spot prices for truckload services average about 62% higher than contract rates. We find key operational and economic factors to be drivers of freight rejection and the shipper-carrier relationship to be a deterrent to freight rejection. We also find that primary and secondary carriers respond differently to these operational and economic factors. We discuss how these insights could be used by a shipper to get better performance and lower cost from their carrier base. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a dynamic and stochastic variant of the traveling purchaser problem where quantity available for each product in each market decreases over time according to a stochastic process. The multiobjective nature of the problem is faced through a hierarchical evaluation of the different objectives. We introduce three variants of a heuristic approach using reoptimization to exploit new information as it becomes available. The proposed approaches are studied under different operating scenarios characterized by the communication technologies at hand and by the level of information available on the state of the world. Extensive computational results show how communication and a good level of information represent valuable tools for a decision maker, and provide interesting guidelines for decision makers involved with similar stochastic and dynamic problems. [ABSTRACT FROM AUTHOR]

We consider the vehicle routing problem with deadlines under travel time uncertainty in the contexts of stochastic and robust optimization. The problem is defined on a directed graph where a fleet of vehicles is required to visit a given set of nodes and deadlines are imposed at a subset of nodes. In the stochastic vehicle routing problem with deadlines (SVRP-D), the probability distribution of the travel times is assumed to be known and the problem is solved to minimize the sum of probability of deadline violations. In the robust vehicle routing problem with deadlines (RVRP-D), however, the exact probability distribution is unknown but it belongs to a certain family of distributions. The objective of the problem is to optimize a performance measure, called lateness index, which represents the risk of violating the deadlines. Although novel mathematical frameworks have been proposed to solve these problems, the size of the problem that those approaches can handle is relatively small. Our focus in this paper is the computational aspects of the two solution schemes. We introduce formulations that can be applied for the problems with multiple capacitated vehicles and discuss the extensions to the cases of incorporating service times and soft time windows. Furthermore, we develop an algorithm based on a branch-and-cut framework to solve the problems. The experiments show that these approaches provide substantial improvements in computational efficiency compared to the approaches in the literature. Finally, we provide a computational comparison to evaluate the solution quality of the SVRP-D and the RVRP-D. The results show that the RVRP-D produces solutions that are very competitive to those obtained by the SVRP-D with a large number of scenarios, whereas much less sensitive to the distributional uncertainty. [ABSTRACT FROM AUTHOR]

We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer's selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open. [ABSTRACT FROM AUTHOR]

We present a large-scale static and deterministic mixed-integer linear programming (MILP) model solving a two-echelon capacitated location-routing problem (2E-CLRP) with modal choice in the context of urban logistics services (ULS). This model aims to support the development of profitable ULS by guiding the strategic decision making of postal operators as they design an optimal facility network and vehicle fleet for the centralized consolidation and transportation of inbound and outbound urban freight flows. After comprehensively analyzing operating data from La Poste, we identify the key determinants of an optimal infrastructure and fleet design for the centralized coordination and consolidation of urban freight flows under a global service time constraint. Further, we discuss the optimal design's sensitivity to changes in the input data and parameters of the 2E-CLRP model. The main theoretical contributions of this work are an optimal routing cost estimation formula and an optimization heuristic. Together these allow us to solve the large-scale MILP problem presented here within a reasonable time and with little loss of precision. [ABSTRACT FROM AUTHOR]

We consider the complex and not-yet-studied issue of building the tactical plan of a two-tiered city logistics system while explicitly accounting for the uncertainty in the forecast demand. We describe and formally define the problem and then propose a general modeling framework, which takes the form of a two-stage stochastic programming formulation, the first stage selecting the first-tier service network design and the general workloads of the intertier transfer facilities, and the second stage determines the actual vehicle routing on the second tier as well as some limited adjustments of the first-stage service design decisions. Four different strategies of adapting the plan to the observed demand are introduced together with the associated recourse formulations. These strategies are then experimentally compared through an evaluation procedure that, based on Monte Carlo principles, mimics the decision process of a priori planning followed by repetitively applying the adjusted plan to the periods of the planning horizon. The performances of the city logistics system under the adjustment strategies are contrasted through performance measures relative to the costs of operating the system, including those of additional vehicle capacity and movements required when the plan does not provide sufficient transportation means, the utilization of the various types of vehicles, the intensity of the vehicle presence within the city, and the utilization of the intertier transfer facilities. The comparisons are discussed both based on the numerical figures obtained through simulation and from the point of view of managerial insights into the implication for managing city logistics physical and human resources. The analysis emphasizes the interest of flexibility in managing resources and operations for the overall performance of the system, discusses the associated trade-offs, and underlines the benefits of consolidation in terms of system efficiency and impact on the city. The comparisons also show that even when demand variability and management constraints are explicitly taken into account, our approach is still able to build good tactical plans. [ABSTRACT FROM AUTHOR]

We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company. This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX. [ABSTRACT FROM AUTHOR]

The multi-trip vehicle routing problem with time windows and release dates is a variant of the multi-trip vehicle routing problem where a time window and a release date are associated with each customer. The release date represents the date when the merchandise requested by a customer becomes available at the depot. The interest for this problem comes from the field of city logistics and the study of delivery systems involving City Distribution Centers (CDC). In these systems, goods are first delivered to a CDC before being transferred to eco-friendly vehicles for final delivery. We propose to address the problem through a population-based algorithm, with a giant tour representation for individuals. An efficient labeling procedure allows turning giant tours into solutions. Experiments demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

We propose a new mathematical model for transport optimization in logistics networks on the tactical level. The main features include accurately modeled tariff structures and the integration of spatial and temporal consolidation effects via a cyclic pattern expansion. Using several graph-based gadgets, we are able to formulate our problem as a capacitated network design problem. To solve the model, we propose a local search procedure that reroutes flow of multiple commodities at once. Initial solutions are generated by various heuristics, relying on shortest path augmentations and LP techniques. As an important subproblem we identify the optimization of tariff selection on individual links, which we prove to be NP-hard and for which we derive exact as well as fast greedy approaches. We complement our heuristics by lower bounds from an aggregated mixed-integer programming formulation with strengthened inequalities. In a case study from the automotive, chemical, and retail industries, we prove that most of our solutions are within a single-digit percentage of the optimum. [ABSTRACT FROM AUTHOR]

This paper addresses the fleet renewal problem and particularly the treatment of uncertainty in the maritime case. A stochastic programming model for the maritime fleet renewal problem is presented. The main contribution is that of assessing whether or not better decisions can be achieved by using stochastic programming rather than employing a deterministic model and using average data. Elements increasing the relevance of uncertainty are also investigated. Tests performed on the case of Wallenius Wilhelmsen Logistics, a major liner shipping company, show that solutions to the model we present perform noticeably better than solutions obtained using average values. [ABSTRACT FROM AUTHOR]

The multicommodity-ring location routing problem (MRLRP) studied in this paper is an NP-hard minimization problem arising in city logistics. The aim is to locate a set of urban distribution centers (UDCs) and to connect them via a ring in which massive flows of goods will circulate. Goods are transported from gates located outside the city to a UDC, and either join a second UDC through the ring before being delivered in electric vans to the final customers or are delivered directly to the customers from the first UDC. The reverse trip with pickup and transportation to the gates is also possible. A delivery service path starts at a particular UDC, then visits a subset of customers and ends at the same UDC, another UDC, or a self-service parking lot (SPL). A pickup route can start from an SPL or a UDC and ends at a UDC. The objective is to minimize the sum of the installation costs of the ring, flow transportation costs, and routing costs. The MRLRP belongs to the class of location-routing problems (LRP). We model it with a set-partitioning-like representation of delivery and pickup trips and arc-flow elements to describe goods transportation in the ring and between the ring and the gates. We present three approaches to solving the MRLRP: an exact method for small-size instances, a matheuristic for instances of a larger size, and a hybrid approach that applies the exact method to the columns output by the matheuristic. Numerical results are provided for an exhaustive set of instances, obtained by extending benchmark instances of the capacitated LRP with additional MRLRP features. [ABSTRACT FROM AUTHOR]

Vehicle routing problems with stochastic travel and service times (VRPSTT) consist of designing transportation routes of minimal expected cost over a network where travel and service times are represented by random variables. Most of the existing approaches for VRPSTT are conceived to exploit the properties of the distributions assumed for the random variables. Therefore, these methods are tied to a given family of distributions and subject to strong modeling assumptions. We propose an alternative way to model travel and service times in VRPSTT without making many assumptions regarding such distributions. To illustrate our approach, we embed it into a state-of-the-art routing engine and use it to conduct experiments on instances with different travel and service time distributions. [ABSTRACT FROM AUTHOR]

This paper introduces a dynamic spatial price equilibrium model that estimates urban freight-related flows for integrated producer-carrier operations that compete in a market where a generic commodity is traded. The model is applicable to cases where suppliers compete in a market by producing a commodity that is delivered to customers by means of delivery tours. The model obtains the patterns of commodity flows, production levels, and delivery tours that maximize economic welfare. The model is then reinterpreted as a Nash equilibrium model, where a set of suppliers deploys strategies involving production and delivery decisions to maximize profits, that is then solved with a heuristic approach that decomposes the interrelated decisions into how much to produce, how best to deliver to customers, and how much to charge for the cargo. Once the suppliers make these decisions, a market-clearing mechanism determines the amount of supplies that the various consumer nodes purchase from the suppliers. At this stage, the suppliers readjust their market strategies in anticipation of the next time period. The process ends when equilibrium is reached. Three different dynamics of the suppliers' decisions on production levels are tested to gain insight into how efficiently each helps to reach the equilibrium solutions. By developing a model that explicitly considers delivery tours, the paper makes a significant contribution to the fields of spatial price equilibrium and freight demand modeling. [ABSTRACT FROM AUTHOR]

The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods. [ABSTRACT FROM AUTHOR]

Today, around 54% of the world's population lives in urban areas. By 2050, this share is expected to go up significantly. As a result, city logistics, which focuses on the efficient and effective transportation of goods in urban areas while taking into account the negative effects on congestion, safety, and environment, is critical to ensuring continued quality of life in cities. We review and discuss a variety of current and anticipated challenges and opportunities of city logistics. We hope this helps shaping an appropriate research agenda and stimulates more researchers to enter this exciting field. [ABSTRACT FROM AUTHOR]

Attended home delivery services face the challenge of providing narrow delivery time slots to ensure customer satisfaction, while keeping the significant delivery costs under control. To that end, a firm can try to influence customers when they are booking their delivery time slot so as to steer them toward choosing slots that are expected to result in cost-effective schedules. We estimate a multinomial logit customer choice model from historic booking data and demonstrate that this can be calibrated well on a genuine e-grocer data set. We propose dynamic pricing policies based on this choice model to determine which and how much incentive (discount or charge) to offer for each time slot at the time a customer intends to make a booking. A crucial role in these dynamic pricing problems is played by the delivery cost, which is also estimated dynamically. We show in a simulation study based on real data that anticipating the likely future delivery cost of an additional order in a given location can lead to significantly increased profit as compared with current industry practice. [ABSTRACT FROM AUTHOR]

In the single truck and trailer routing problem with satellite depots (STTRPSD), a truck with a detachable trailer based at a main depot must serve the demand of a set of customers accessible only by truck. Therefore, before serving the customers, it is necessary to detach the trailer in an appropriate parking place (called either a satellite depot or a trailer point) and transfer goods between the truck and the trailer. This problem has applications in milk collection for farms that cannot be reached using large vehicles. In this work we present an integer programming formulation of the STTRPSD. This formulation is tightened with several families of valid inequalities for which we have developed different (exact and heuristic) separation procedures. Using these elements, we have implemented a branch-and-cut algorithm for the solution of the STTRPSD. A computational experiment with published instances shows that the proposed branch-and-cut algorithm consistently solves problems with up to 50 customers and 10 satellite depots, and it has also been able to solve instances with up to 20 satellite depots and 100 clustered customers. [ABSTRACT FROM AUTHOR]

We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances. [ABSTRACT FROM AUTHOR]

In this paper, we study a novel toll setting policy to regulate hazardous material (hazmat) transportation, where the regulator (e.g., a government authority) aims at minimizing not only the network total risk but also at spreading the risk in an equitable way over a given road network. The idea is to use a toll setting policy to discourage carriers transporting hazmat from overloading portions of the network with the consequent increase of the risk exposure of the population involved. Specifically, we assume that the toll paid by a carrier on a network link depends on the usage of that link by all carriers. Therefore the route choices of each carrier depend on the other carrier's choices, and the tolls deter the carriers from using links with a high total risk. The resulting model is a mathematical programming with equilibrium constraints (MPEC) problem, where the inner problem is a Nash equilibrium problem (game) having as players the carriers, each one wishing to minimize his or her travel cost (including tolls); the outer problem is addressed by the government authority, whose aim is finding the link tolls that induce the carriers to choose route plans that minimize both the network total risk and the maximum link total risk among the network links (to address risk equity). To guarantee the stability of the solution, we study conditions for the existence and uniqueness of the Nash equilibrium, and propose a local search heuristic for the MPEC problem. Computational results are carried out on a real road network, comparing the performance of our toll setting policy with the toll setting approach proposed in the literature. [ABSTRACT FROM AUTHOR]

We develop restocking-based rollout policies to make real-time, dynamic routing decisions for the vehicle routing problem with stochastic demand and duration limits. Leveraging dominance results, we develop a computationally tractable method to estimate the value of an optimal restocking policy along a fixed route. Embedding our procedure in rollout algorithms, we show restocking-based rollout outperforms a priori-based rollout, demonstrating the value of explicitly considering preemptive capacity replenishment in a rollout approach for dynamic routing. We also demonstrate the effectiveness of basic local search versus more sophisticated mechanisms for the heuristic component of the rollout procedure. [ABSTRACT FROM AUTHOR]

The Last Mile Problem refers to the provision of travel service from the nearest public transportation node to a home or office. We study the supply side of this problem in a stochastic setting, with batch demands resulting from the arrival of groups of passengers who request last-mile service at urban rail stations or bus stops. Closed-form approximations are derived for the performance of Last Mile Transportations Systems (LMTS) as a function of the fundamental design parameters of such systems. An initial set of results is obtained for the case wherein a fleet of vehicles of unit capacity provides the Last-Mile service, and each delivery route consists of a simple round trip between the rail station or bus stop and a single passenger's destination. These results are then extended to the general case in which the capacity of a vehicle is a small number (up to 20). It is shown through comparisons with simulation results that the approximations perform consistently well for a broad and realistic range of input values and conditions. These expressions can therefore be used for the preliminary planning and design of an LMTS, especially for determining approximate resource requirements, such as the number of vehicles/servers needed to achieve some prespecified level of service, as measured by the expected waiting time until a passenger is picked up from the station or delivered to her destination. [ABSTRACT FROM AUTHOR]

This paper considers the classical vehicle routing problem (VRP) where the vehicle capacity is not fixed. Indeed, at the moment of acquiring (or renting) the vehicle that will serve all customers, there is some freedom of choice. A larger vehicle capacity implies a lower total distance travelled but larger operating costs. The reverse is true for a smaller vehicle. This paper gives an approach to select the best capacity and the best route to minimize a function of the acquisition cost and travelled distance. We first consider an enumerative approach, which consists of solving a sequence of VRPs, starting from the one having the largest capacity. The number of VRPs to solve using this approach is unknown. Based on computational experiments, this number is mostly large in our benchmark instances. We then proceed to a direct approach based on the two-index formulation of the VRP. We introduce several valid inequalities that allow us to have an integer linear programming formulation of the VRP with fixed vehicle capacity. We describe separation procedures for these inequalities. We conclude with computational results that confirm the utility of these inequalities when solving benchmark VRP instances. [ABSTRACT FROM AUTHOR]

This paper studies the real-time crew rescheduling problem in case of large-scale disruptions. One of the greatest challenges of real-time disruption management is the unknown duration of the disruption. In this paper we present a novel approach for crew rescheduling where we deal with this uncertainty by considering several scenarios for the duration of the disruption. The rescheduling problem is similar to a two-stage optimization problem. In the first stage, at the start of the disruption, we reschedule the plan based on the optimistic scenario (i.e., assuming the shortest possible duration of the disruption), while taking into account the possibility that another scenario will be realized. We require a prescribed number of the rescheduled crew duties (a sequential list of tasks which have to be performed by a single crew member) to be recoverable. The true duration of the disruption is revealed in the second stage. By the recoverability of the duties, we expect that the first stage solution can easily be turned into a schedule that is feasible for the realized scenario. We demonstrate the effectiveness of our approach by an application in real-time railway crew rescheduling. The ideas of this paper generalize to certain vehicle rescheduling and manufacturing problems where timetabled tasks which have a fixed start and end location are to be carried out by a given number of servers. We test our approach on a number of instances of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. The numerical experiments show that the approach indeed finds schedules which are easier to adjust if it turns out that another scenario than the optimistic one is realized for the duration of the disruption. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The elementary shortest path problem with resource constraints (ESPPRC) is an NP-hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state-of-the-art algorithms for the ESPPRC on the well-known Solomon's test bed for the VRPTW. [ABSTRACT FROM AUTHOR]

The growth of literature in the field of quality of service in the public transport (PT) sector shows increasing concern for a better understanding of the factors affecting service quality (SQ) in PT organizations and companies. A large variety of approaches to SQ have been developed in recent years owing to the complexity of the concept; the broad range of attributes required to evaluate SQ; and the imprecision, subjectivity, and heterogeneous nature of the data used to analyze it. Most of these approaches are based on customer satisfaction surveys. This paper seeks to summarize the evolution of research and current thinking as it relates to the different methodological approaches for SQ evaluation in the PT sector over the years and to provide a discussion of future directions. [ABSTRACT FROM AUTHOR]

This paper presents the hub line location problem in which the location of a set of hub facilities connected by means of a path (or line) is considered. Potential applications arise in the design of public transportation and rapid transit systems, where network design costs greatly dominate routing costs and thus full interconnection of hub facilities is unrealistic. Given that service time is the predominant objective in these applications, the problem considers the minimization of the total weighted travel time between origin/destination nodes while taking into account the time spent to access and exit the hub line. An exact algorithm based on a Benders decomposition of a strong path-based formulation is proposed. The standard decomposition method is enhanced through the incorporation of several features such as a multicut strategy, an efficient algorithm to solve the subproblem and to obtain stronger optimality cuts, and a Benders branch-and-cut scheme that requires the solution of only one master problem. Computational results obtained on benchmark instances with up to 100 nodes confirm the efficiency of the proposed algorithm, which is considerably faster and able to solve larger instances than a general purpose solver. [ABSTRACT FROM AUTHOR]

We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for multiple criteria, such as arrival time and number of transfers. Existing algorithms consider this as a graph problem and solve it using various graph search algorithms. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Starting from arrival time and number of transfers as criteria, it can be easily extended to handle flexible departure times or arbitrary additional criteria. As practical examples we consider fare zones and reliability of transfers. When run on complex public transportation networks (such as London), RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications. [ABSTRACT FROM AUTHOR]

There has been extensive research on the optimal design of road congestion pricing schemes based on traffic network equilibrium models. Since travel demands are closely related to the locations of workplace and residence, it is of both theoretical and practical importance to extend the optimization approach to treat location choices as well as travel route choices. This paper addresses the problem of optimal location of housing supply and transportation network pricing in an integrated location and transportation model with heterogeneous households that have different values of travel time. In the model, housing exhibits external economies and diseconomies of scale, depending on the population density in residential zones. It is shown that in such a model the marginal cost pricing principle applied to internalize these externalities in general results in local optima of social surplus. Optimization algorithms based on sensitivity analysis are proposed to find combinations of housing supply patterns and road tolls that optimize social surplus under various conditions. A numerical example is given to illustrate the proposed method. The potential policy implications of the optimization approach are examined and compared with that of the marginal cost pricing principle. [ABSTRACT FROM AUTHOR]

Public transportation is one of the most essential services in urban areas. The average passenger waiting time at a stop is an important criterion in evaluating the quality of public transportation systems. Accurate measurement of the average waiting time (AWT) at stops leads to more appropriate and timely schedules. Researchers in the past developed formulations for measuring the AWT at stops based on the assumptions that passengers arrive at stops in a uniform manner and buses arrive at stops independently. Studies on transportation systems in different cities indicate that using these formulations does not result in an accurate measure of the AWT and that there is a significant difference between the observed AWT and the one estimated by these formulations. Researchers related the cause of this discrepancy to the violation of the assumptions of uniform passenger arrival times and independent headways. We show that when the number of buses is not large (even when these assumptions hold true) the existing formulations still lack adequate accuracy. In this paper, we examine the process of formula development that resulted in a formulation that overestimates the AWT; we then propose accurate formulas for estimating the AWT with dependent and independent headways. A discrete simulation model has also been developed to further verify the inaccuracy of the existing formulations and to evaluate the performance of the proposed formulations. Furthermore, as a case study, the AWT at a bus stop in the Tehran bus transportation system has been studied and the accuracy of the proposed formulations has been examined and compared with that of the existing one. [ABSTRACT FROM AUTHOR]

A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypical vehicle-routing problem with ordinary and dynamic time windows. For the first time (to our knowledge), both ordinary and dynamic time windows are handled in the column-generation subproblem. For the solution, an effective column-generation pricing procedure is derived that allows fast shortest-path computations due to new dominance rules. The new approach is compared with alternative column-generation algorithms that handle dynamic time windows either as constraints of the master program or with less effective labeling procedures. Computational experiments indicate the superiority of the new approach. [ABSTRACT FROM AUTHOR]

We study a real-world distribution problem arising in the automotive field in which cars, trucks, and other vehicles have to be loaded onto auto-carriers and then delivered to dealers. The solution of the problem involves both the computation of the routing of the auto-carriers along the road network and the determination of a feasible loading for each carrier. We solve the problem by means of an iterated local search algorithm that makes use of several inner local search strategies for the routing part and mathematical modeling and enumeration techniques for the loading part. Extensive computational results on real-world instances show that good savings on the total cost can be obtained within small computational efforts. [ABSTRACT FROM AUTHOR]

We consider curbside bus stops of the kind that serve multiple bus routes and that are isolated from the effects of traffic signals and other stops. A Markov chain embedded in the bus queueing process is used to develop steady-state queueing models of this stop type, as illustrated by two special cases. The models estimate the maximum number of buses that can arrive at and serve a stop and still satisfy a specified target of average bus delay. These models can be used to determine, for example, a stop's suitable number of bus berths, given the bus demand and the specified delay target. The solutions for the two cases are used to derive a closed-form, parsimonious approximation model for general cases. This approximation matches simulations reasonably well for many conditions that arise in real settings; differences of less than 10% were common. Our results unveil how suitable choices for the number of bus berths are influenced by both the variation in the time that buses spend serving passengers at the stop and the specified delay target. The models further show why the proxy measure commonly used for the delay target in previous bus stop studies is a poor one. [ABSTRACT FROM AUTHOR]

The vehicle routing problem with divisible deliveries and pickups is a new and interesting model within reverse logistics. Each customer may have a pickup and delivery demand that have to be served with capacitated vehicles. The pickup and the delivery quantities may be served, if beneficial, in two separate visits. The model is placed in the context of other delivery and pickup problems and formulated as a mixed-integer linear programming problem. In this paper, we study the savings that can be achieved by allowing the pickup and delivery quantities to be served separately with respect to the case where the quantities have to be served simultaneously. Both exact and heuristic results are analysed in depth for a better understanding of the problem structure and an average estimation of the savings due to the possibility of serving pickup and delivery quantities separately. [ABSTRACT FROM AUTHOR]

In this paper we introduce the dial-a-ride problem with split requests and profits (DARPSRP). Users place transportation requests, specifying a pickup location, a delivery location, and a time window for either of the two. Based on maximum user ride time considerations, the second time window is generated. A given fleet of vehicles, each with a certain capacity, is available to serve these requests, and maximum route duration constraints have to be respected. Each request is associated with a revenue and the objective is to maximize the total profit, that is, the total revenue minus the total costs. Transportation requests involving several persons may be split if it is beneficial to do so. We formulate the DARPSRP as a mixed-integer program using position variables and in terms of a path-based formulation. For the solution of the latter, we design a branch-and-price algorithm. The largest instance solved to optimality, when applied to available instances from the literature, has 40 requests; when applied to newly generated instances, the largest instance solved to optimality consists of 24 requests. To solve larger instances a variable neighborhood search algorithm is developed. We investigate the impact of request splitting under different geographical settings, assuming favorable settings for request splitting in terms of the number of people per request. The largest benefits from request splitting are obtained for problem settings exhibiting clustered customer locations. [ABSTRACT FROM AUTHOR]

This paper presents a mixed-integer programming model for a variant of the pickup and delivery problem with time windows. The fleet is assumed to be heterogeneous with a novel feature that allows the vehicles to be configured before service begins to handle various types of demand. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center, as well as to secondary facilities for rehabilitative and medical treatment. The number of participants and support equipment that a van can accommodate depends on how it is configured. An exact method is introduced based on branch and price and cut. At each node in the search tree, the master problem is solved by column generation to find a lower bound. To improve the bound, subset-row inequalities are applied to the variables of the master problem. Columns are generated by solving the pricing subproblems with a labeling algorithm enhanced by new dominance conditions. Local search on the current set of columns is used to quickly find promising additions. Implementation details and ways to improve the performance of the overall procedure are discussed. Testing was done on a set of real instances as well as a set of randomly generated instances with up to 50 customer requests. The results show that optimal solutions are obtained in the majority of cases. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. The algorithm relies on a reformulation based on q-routes that combines two important features. First, it overcomes symmetry issues observed in a formulation coming from a previous study of the problem. Second, it is strengthened with several classes of valid inequalities. As a result, the branch-and-cut-and-price implementation compares favorably with previous exact solution approaches for the problem--namely, two branch-and-price algorithms and a branch-and-cut method. Overall, 10 new optimality certificates and 8 new best upper bounds are provided in this study. New best lower bounds are also presented for all instances in the hardest test set from the literature. [ABSTRACT FROM AUTHOR]

This paper presents the formulation of a new optimization problem designated as the express minibus problem, which intends to form small groups of clients with compatible boarding/exiting points in time and space for a new type of urban mobility service. This new transport option, as a competitive alternative to the private car, aims to provide almost direct services between dispersed demand poles in places where high-capacity and efficient public transport options are scarce, thus combining the major strengths of both public transport and private vehicles. Conventional public transport systems can present efficient space and energy consumption, whereas private vehicles have high levels of flexibility, are fast, and are always available. The proposed algorithm aims at assessing the potential demand of this new service by developing a clustering algorithm in which the groups of clients formed for each minibus route should present the following characteristics: there is a small number of boarding and exiting points, where in each point there is only boarding or alighting; boarding points should be close to each other, as well as the exiting points; there must be a reasonable distance between the last boarding point and the first exiting point; the average load factor must be high; and for all clients the overall detour time relative to the direct service should be small. This paper presents the rationale and structure of the clustering algorithm, followed by an application for the Lisbon metropolitan area during the morning peak, which could be adapted to the afternoon peak with some slight modifications. [ABSTRACT FROM AUTHOR]

In this paper, we develop optimal electricity storage control policies to manage charging and discharging activities for plug-in hybrid electric vehicles for the benefit of an energy market participant. We first develop models for both risk-neutral and risk-averse aggregators to participate only in a real-time market. The proposed models capture the impact of the charging and discharging activities on real-time electricity prices. Next, we extend our study to the case in which aggregators participate in both the real-time and day-ahead markets. For each developed model, we analyze the properties of the optimal objective value function, prove the existence and uniqueness of the optimal policy, and explore the corresponding optimal policy structure. Moreover, through numerical studies, we explore insights into how electricity prices are influenced by charging and discharging activities. In particular, we observe that aggregated charging/discharging activities with market-impact consideration could reduce the variance of the real-time electricity prices more efficiently, as compared to individual activities. In addition, considering market impact, an aggregator tends to use less electricity storage. Finally, it is beneficial to let an aggregator control the electricity storage and participate in both the real-time and day-ahead markets, instead of participating only in the real-time market. [ABSTRACT FROM AUTHOR]

Meeting the 21st century's challenges of climate change and scarcity of crude oil requires a better understanding of the forces that ensure a successful market introduction of electric vehicles. Against this background, we develop a hybrid simulation approach to estimate the evolution of market shares of electric vehicles. The approach integrates a system dynamics model with an agent-based discrete choice model. System dynamics is used to model the interdependencies between consumer choice, consumer awareness, evolution of powertrain technologies, and service station availability on the macro level. By integrating the agent-based discrete choice model we refine the model parts of consumer choice and consumer awareness. This allows for considering individual consumer choices. Based on real-world data, we apply the model to the established and saturated German market, where replacement purchases dominate. This way we study the interdependencies between the evolution on the macro level and (1) individual replacement purchases as well as (2) heterogeneous consumer behavior. We show that both effects have a clear influence on the market share evolution of electric vehicles. The results indicate that neglecting individual consumer choices in aggregated system models may lead to systematically wrong estimations of the evolution of the market shares of electric vehicles. [ABSTRACT FROM AUTHOR]

Properly determining the driving range is critical for accurately predicting the sales and social benefits of battery electric vehicles (BEVs). This study proposes a framework for optimizing the driving range by minimizing the sum of battery price, electricity cost, and range limitation cost--referred to as the "range-related cost"--as a measurement of range anxiety. The objective function is linked to policy-relevant parameters, including battery cost and price markup, battery utilization, charging infrastructure availability, vehicle efficiency, electricity and gasoline prices, household vehicle ownership, daily driving patterns, discount rate, and perceived vehicle lifetime. Qualitative discussion of the framework and its empirical application to a sample (N = 361664) representing new car drivers in the United States is included. The quantitative results strongly suggest that ranges of less than 100 miles are likely to be more popular in the BEV market for a long period of time. The average optimal range among U.S. drivers is found to be largely inelastic. Still, battery cost reduction significantly drives BEV demand toward longer ranges, whereas improvement in the charging infrastructure is found to significantly drive BEV demand toward shorter ranges. The bias of a single-range assumption and the effects of range optimization and diversification in reducing such biases are both found to be significant. [ABSTRACT FROM AUTHOR]

Meeting charging demands of large electric vehicle fleets will raise electrical load significantly and may pose challenges for today's power system. Appropriate coordination of electric vehicle charging can reduce these threats. Acknowledging the interdependency between the transportation and the power system created by electric vehicles, we develop a charging coordination model based on German mobility data. We extend the prior work by explicitly accounting for both the temporal and the spatial dimension. We are thus able to analyze the loads from price-based EV fleet charging while at the same time accounting for distribution grid constraints. Furthermore, we propose a heuristic charging strategy based on limited trip and price information. Our results show that the sole use of time-based electricity prices for the coordination of electric vehicle charging produces high load spikes independent of the charging strategies and power levels. These peaks are induced by simultaneous charging activity and may cause stability problems within distribution grids in residential areas. To mitigate these load spikes, we introduce a spatial price component that reflects local capacity utilization. These local prices induce both a temporal and spatial shift of charging activity that mitigates the load spikes. [ABSTRACT FROM AUTHOR]

In this paper, we propose a vehicle-scheduling model for electric transit buses with either battery swapping or fast charging at a battery station, and a vehicle-scheduling model with the maximum route distance constraint for compressed natural gas, diesel, or hybrid-diesel buses. Both of these scheduling models are NP-hard. We develop column-generation-based algorithms to solve the scheduling problems. We conduct extensive case studies based on real-world instances and instances randomly generated in a practical setting. Our computational experiments show that our algorithms demonstrate very good computational performances. We also use real-world transit data to systematically analyze the number of buses needed, the total operational costs, and the vehicle emissions generated when compressed natural gas, diesel, hybrid, or electric buses are used in service. [ABSTRACT FROM AUTHOR]

In this paper we use Bayes estimates of a multinomial probit model with fully flexible substitution patterns to forecast consumer response to ultra-low-emission vehicles. In this empirical application of the probit Gibbs sampler, we use stated-preference data on vehicle choice from a Germany-wide survey of potential light-dutyvehicle buyers using computer-assisted personal interviewing. We show that Bayesian estimation of a multinomial probit model with a full covariance matrix is feasible for this medium-scale problem and provides results that are very similar to maximum simulated likelihood estimates. Using the posterior distribution of the parameters of the vehicle choice model as well as the GHK simulator, we derive the choice probabilities of the different alternatives. We first show that the Bayes point estimates of the market shares reproduce the observed values. Then we define a base scenario of vehicle attributes that aims to represent an average of the current vehicle choice situation in Germany. Consumer response to qualitative changes in the base scenario is subsequently studied. In particular, we analyze the effect of increasing the network of service stations for charging electric vehicles as well as for refueling hydrogen. The result is the posterior distribution of the choice probabilities that represent adoption of the energy-efficient technologies. [ABSTRACT FROM AUTHOR]

Passengers using public transport systems often experience waiting times when transferring between two scheduled services. In this paper we propose a planning approach that seeks to obtain a favourable trade-off between the two contrasting objectives, passenger service and operating cost, by modifying the timetable. The planning approach is referred to as the simultaneous vehicle scheduling and passenger service problem (SVSPSP). The SVSPSP is modelled as an integer programming problem and solved using a large neighborhood search metaheuristic. The proposed framework is tested on data inspired by the express-bus network in the Greater Copenhagen area. The results are encouraging and indicate a potential decrease of passenger transfer waiting times in the network of up to 20%, with the vehicle scheduling costs remaining mostly unaffected. [ABSTRACT FROM AUTHOR]

The estimation of random parameters by means of mixed logit models is now current practice for the analysis of transportation behaviour. One of the most straightforward applications is the derivation of willingness-to-pay distribution over a heterogeneous population, an important element for dynamic tolling strategies on congested networks. In numerous practical cases, the underlying discrete choice models involve parametric distributions that are a priori specified and whose parameters are estimated. This approach can however lead to many problems for realistic interpretation, such as negative value of time, etc. In this paper, we propose to capture the randomness present in the model by using a new nonparametric estimation method, based on the approximation of inverse cumulative distribution functions. This technique is applied to simulated data, and the ability to recover both parametric and nonparametric random vectors is tested. The nonparametric mixed logit model is also used on real data derived from a stated preference survey conducted in the region of Brussels (Belgium). The model presents multiple choices and is estimated on repeated observations. The obtained results provide a more realistic interpretation of the observed behaviours. [ABSTRACT FROM AUTHOR]

The impact of variable speed limits (VSL) on aggregate traffic flow behaviour on motorways is shown to bear similarities to the impact of ramp metering, in particular, when addressing potentially active bottlenecks. A quantitative model of the VSL impact is proposed that allows for VSL to be incorporated in a macroscopic second-order traffic flow model as an additional control component. The integrated motorway network traffic control problem involving ramp metering and VSL control measures is formulated as a constrained discrete-time optimal control problem and is solved efficiently even for large-scale networks by a suitable feasible direction algorithm. An illustrative example of a hypothetical motorway stretch is investigated under different control scenarios, and it is shown that traffic flow efficiency can be substantially improved when VSL control measures are used, particularly in integration with coordinated ramp metering. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various reports published within the issue on topics including modeling, planning, and management of freight transportation and logistics systems, fleet management problems, and vehicle routing.

In the 1960s, Braess showed that the overall system performance of a transportation network can be degraded when a new link is added to the network, given that travelers choose their routes based on the user equilibrium (UE) principle. This phenomenon is often referred to as Braess' paradox (BP). The original five-link BP network has been studied extensively with static link performance functions. In this paper, we revisit the original BP network with a dynamic point-queue model and examine whether the results from the static model would hold for the case with time-dependent queues. For this purpose, we solve the BP problem with the consideration of dynamic queuing that leads the system to a steady state while satisfying the dynamic user equilibrium (DUE) condition at every instant. Our results indicate that the locations of congestion, or "hot spots," of the system are sensitive to the capacity of each link in an intricate manner. The "surprising result" reported in previous studies with link performance functions, that a system can spontaneously grow out of Braess' paradox if the demand is sufficiently high, does not occur with time-dependent queues. Instead, we show that queues in different stages have different impacts on the system performance. The implication of this result is discussed in the context of developing proactive dynamic traffic control strategies that can eliminate the negative impact of BP while keeping the system operating at the DUE condition. Even though this study focuses on the original five-link network, the results illustrate the potential pitfalls of extending insights developed from a static framework for dynamic traffic and the importance of studying the problem with a dynamic framework for real-time traffic control. [ABSTRACT FROM AUTHOR]

This paper studies the arc-routing problem that arises in small-package delivery. In practice, each service provider is encouraged to follow a master route-a predesigned sequence of street addresses-over an extended planning horizon (more than one day). The objective here is to construct efficient master routes. The focus on arc routing offers two advantages. First, real-world vehicle routing takes place over a street network, rather than in Euclidean space. Second, there are, typically, many fewer streets than customer locations. Currently, a deterministic arc-routing problem (DARP) model is used to solve the problem. However, this approach ignores the uncertainty in the street segment presence probability-the probability that a street segment requires (i.e., there is a demand for) a visit on a particular day. We introduce two new models, namely, the probabilistic arc-routing problem (PARP) model and the multiday arc-routing problem (MARP) model, which take into account the street segment presence probabilities. PARP attempts to minimize the expected length of the master route. It assumes that the street segment presence probabilities are independent. This model can require excessive amounts of computation time. On the other hand, MARP tries to minimize average length of the master route over prespecified days. This model can also be viewed as a Monte Carlo simulation approximation of the PARP. This approximation significantly reduces the computational burden. Additionally, by utilizing historical data, MARP incorporates real-world correlations among the street segment presence probabilities. Our computational results show that PARP and MARP may produce more efficient master routes than DARP by taking demand uncertainty into account. [ABSTRACT FROM AUTHOR]