1,721,390 research outputs found
A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
Full text linkGiven a connected undirected graph G=(V,E), the Minimum Branch Vertices Problem (MBVP) asks for a spanning tree of G with the minimum number of vertices having degree greater than two in the tree. These are called branch vertices. This problem, with applications in the context of optical networks, is known to be NP-hard. We model the MBVP as an integer linear program, with undirected variables, we derive valid inequalities and we prove that some of these are facet defining. We then develop a hybrid formulation containing undirected and directed variables. Both models are solved with branch-and-cut. Comparative computational results show the superiority of the hybrid formulation
A continuous approximation model for the fleet composition problem
No full textThis paper presents a continuous approximation model to determine the long-term vehicle fleet composition needed to perform distribution activities. The problem is a realistic variant of the vehicle routing problem, in which the fleet size and mix are also decision variables. The types of vehicles differ in terms of their capacities, fixed costs and variable costs. The objective is to minimize the total cost, subject to capacity and route duration constraints. We assume customers are distributed over a circular service region partitioned into zones, each of which is serviced by a single vehicle. The routing costs are assessed through a continuous approximation model. We present a mixed integer non-linear formulation for the problem, followed by computationally efficient upper and lower bounding procedures. The performance of the model and of its bounds is assessed on several test instances. © 2012 Elsevier Ltd
Exact solution of the evasive flow capturing problem
Full text linkThe Evasive Flow Capturing Problem is defined as the problem of locating a set of law enforcement facilities on the arcs of a road network to intercept unlawful vehicle flows traveling between origin-destination pairs, who in turn deviate from their route to avoid any encounter with such facilities. Such deviations are bounded by a given tolerance. We first propose a bilevel program that, in contrast to previous studies, does not require a priori route generation. We then transform this bilevel model into a single-stage equivalent model using duality theory to yield a compact formulation. We finally reformulate the problem by describing the extreme rays of the polyhedral cone of the compact formulation and by projecting out the auxiliary variables, which leads to facet-defining inequalities and a cut formulation with an exponential number of constraints. We develop a branch-and-cut algorithm for the resulting model, as well as two separation algorithms to solve the cut formulation. Through extensive experiments on real and randomly generated networks, we demonstrate that our best model and algorithm accelerate the solution process by at least two orders of magnitude compared with the best published algorithm. Furthermore, our best model significantly increases the size of the instances that can be solved optimally
Charge scheduling for electric freight vehicles
Full text linkWe consider a fleet of electric freight vehicles (EFVs) that must deliver goods to a set of customers over the course of multiple days. In an urban environment, EFVs are typically charged at a central depot and rarely use public charging stations during delivery routes. Therefore, the charging schedule at the depot must be planned ahead of time so as to allow the vehicles to complete their routes at minimal cost. Vehicle fleet operators are subject to commercial electricity rate plans, which should be accounted for in order to provide an accurate estimation of the energy-related costs and restrictions. In addition, high vehicle utilization rates can accelerate battery aging, thereby requiring degradation mitigation considerations. We develop and solve a comprehensive mathematical model that incorporates a large variety of features associated with the use of EFVs. These include a realistic charging process, time-dependent energy costs, battery degradation, grid restrictions, and facility-related demand charges. Extensive numerical experiments are conducted in order to draw managerial insights regarding the impact of such features on the charging schedules of EFVs
Route and speed optimization for autonomous trucks
Full text linkAutonomous vehicles, and in particular autonomous trucks (ATs), are an emerging technology that is becoming a reality in the transportation sector. This paper addresses the problem of optimizing the routes and the speeds of ATs making deliveries under uncertain traffic conditions. The aim is to reduce the cost of emissions, fuel consumption and travel times. The traffic conditions are represented by a discrete set of scenarios, using which the problem is modeled in the form of two-stage stochastic programming formulations using two different recourse strategies. The strategies differ in the amount of information available during the decision making process. Computational results show the added value of stochastic modeling over a deterministic approach and the quantified benefits of optimizing speed
Delivery man problem and cumulative matroids
No full textGiven a complete directed graph G = (V,A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v1, to every vertex of V, including v1 itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimally with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods
50th Anniversary Invited Article—Goods distribution with electric vehicles: Review and research perspectives
No full textSince 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
Long-haul vehicle routing and scheduling with idling options
No full textThis paper introduces the vehicle routing and truck driver scheduling problem with idling options, an extension of the long-haul vehicle routing and truck driver scheduling problem with a more comprehensive objective function that accounts for routing cost, driver cost and idling cost, i.e., the cost associated with energy supply used to maintain drivers' comfort when the vehicle is not moving. For the idling cost, we consider Electrified Parking Space (EPS) and Auxiliary Power Unit (APU) usage costs. The use of EPSs or APUs avoids keeping the engine running while the vehicle is not moving. We develop a multi-start matheuristic algorithm that combines adaptive large neighborhood search and mixed integer linear programming. We present extensive computational results on instances derived from the Solomon test bed
The traveling salesman problem with pickup and delivery and first-in-first-out loading
No full textThis paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a first-in-first-out fashion. It provides an integer programming formulation of the problem. It also describes five operators for improving a feasible solution, and two heuristics that utilize these operators: a probabilistic tabu search algorithm, and an iterated local search algorithm. The heuristics are evaluated on data adapted from TSPLIB instance
- …
