1,721,487 research outputs found
A Hybrid Metaheuristic for Single Truck and Trailer Routing Problems
Full text linkIn this paper, we propose a general solution approach for a broad class of vehicle routing problems that all use a single vehicle, composed of a truck and a detachable trailer, to serve a set of customers with known demand and accessibility constraints. A more general problem, called the extended single truck and trailer routing problem (XSTTRP), is used as a common baseline to describe and model this class of problems. In particular, the XSTTRP contains, all together, a variety of vertex types previously considered only separately: truck customers, vehicle customers with and without parking facilities, and parking-only locations. To solve the XS1TRP, we developed a fast and effective hybrid metaheuristic, consisting of an iterative core part, in which routes that define high-quality solutions are stored in a pool. Eventually, a set-partitioning-based postoptimization selects the best combination of routes that forms a feasible solution from the pool. The algorithm is tested on extensively studied problems from the literature, such as the multiple depot vehicle routing problem, the location routing problem, the single truck and trailer routing problem with satellite depots, and the single truck and trailer routing problem. Finally, computational results and a thorough analysis of the main algorithm's components on newly designed XSTTRP instances are provided. The obtained results show that the proposed hybrid metaheuristic is highly competitive with previous approaches designed to solve specific specialized problems, both in terms of computing time and solution quality
A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems
Full text linkIn this paper, we propose a fast and scalable, yet effective, metaheuristic called FILO to solve large-scale instances of the Capacitated Vehicle Routing Problem. Our approach consists of a main iterative part, based on the Iterated Local Search paradigm, which employs a carefully designed combination of existing acceleration techniques, as well as novel strategies to keep the optimization localized, controlled, and tailored to the current instance and solution. A Simulated Annealing-based neighbor acceptance criterion is used to obtain a continuous diversification, to ensure the exploration of different regions of the search space. Results on extensively studied benchmark instances fromthe literature, supported by a thorough analysis of the algorithm's main components, show the effectiveness of the proposed design choices, making FILO highly competitive with existing stateof- the-art algorithms, both in terms of computing time and solution quality. Finally, guidelines for possible efficient implementations, algorithm source code, and a library of reusable components are open-sourced to allow reproduction of our results and promote further investigations.</p
Branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs
No full textWe consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP. Effective implementation of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature
An exact algorithm for a rich vehicle routing problem with private fleet and common carrier
No full textThe vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.</p
Vehicle Routing: Problems, Methods, and Applications
No full textVehicle routing problems, among the most studied in combinatorial optimization, arise in many practical contexts (freight distribution and collection, transportation, garbage collection, newspaper delivery, etc.). Operations researchers have made significant developments in the algorithms for their solution, and Vehicle Routing: Problems, Methods, and Applications, Second Edition reflects these advances. The text of the new edition is either completely new or significantly revised and
provides extensive and complete state-of-the-art coverage of vehicle routing by those who have done most of the innovative research in the area;
emphasizes methodology related to specific classes of vehicle routing problems and, since vehicle routing is used as a benchmark for all new solution techniques, contains a complete overview of current solutions to combinatorial optimization problems;
includes several chapters on important and emerging applications, such as disaster relief and green vehicle routing
An optimization approach for district heating strategic network design
Full text linkDistrict heating systems provide the heat generated in a centralized location to a set of users for their residential and commercial heating requirements. Heat distribution is generally obtained by using hot water or steam flowing through a closed network of insulated pipes and heat exchange stations at the users' locations. The use of optimization techniques for the strategic design of such networks is strongly motivated by the high cost of the required infrastructures but is particularly challenging because of the technical characteristics and the size of the real world applications. We present a mathematical model developed to support district heating system planning. The objective is the selection of an optimal set of new users to be connected to an existing thermal network, maximizing revenues and minimizing infrastructure and operational costs. The model considers steady state conditions of the hydraulic system and takes into account the main technical requirements of the real world application. Results on real and randomly generated benchmark networks are discussed
The VeRoLog Solver Challenge 2019
No full textThe VeRoLog Solver Challenge 2019 is the 4th solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics. The challenge is organized in cooperation with ORTEC. On behalf of the organizing committee, the authors report on the problem and organization of the challenge
Comparison between calcium and barium alginate capsules as carrier for swine spermatozoa in artifical insemination
No full textValid inequalities for the fleet size and mix vehicle routing problem with fixed costs
No full textIn the well-known vehicle routing problem (VRP), a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instance
- …
