共查询到20条相似文献,搜索用时 15 毫秒
1.
Diego Cattaruzza Nabil Absi Dominique Feillet Thibaut Vidal 《European Journal of Operational Research》2014
We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints. 相似文献
2.
In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search. 相似文献
3.
蚂蚁算法在带时间窗车辆路径问题中的应用研究 总被引:4,自引:0,他引:4
李全亮 《数学的实践与认识》2006,36(10):173-178
蚂蚁算法是近年来新出现的一种随机型搜索寻优算法.自从在旅行商等著名问题中得到富有成效的应用之后,已引起人们越来越多的关注和重视.本文将这种新型的生物优化思想扩展到物流管理中的带时间窗车辆路径问题,从数值计算上探索了蚂蚁算法的优化能力,获得了满意的效果. 相似文献
4.
In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each
route, both a capacity and a total-distance-travelled limit.
Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling
Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position, thus leaving an equal number of
``empty holes' in the tour; (b) optimally re-assign the removed nodes to the empty holes through the efficient solution of
a min-sum assignment (weighted bipartite matching) problem. We first extend the Sarvanov-Doroshko method to DCVRP, and then
generalize it. Our generalization involves a procedure to generate a large number of new sequences through the extracted nodes,
as well as a more sophisticated ILP model for the reallocation of some of these sequences. An important feature of our method
is that it does not rely on any specialized ILP code, as any general-purpose ILP solver can be used to solve the reallocation
model.
We report computational results on a large set of capacitated VRP instances from the literature (with symmetric/asymmetric
costs and with/without distance constraints), along with an analysis of the performance of the new method and of its features.
Interestingly, in 13 cases the new method was able to improve the best-know solution available from the literature.
Work supported by M.I.U.R. and by C.N.R., Italy. 相似文献
5.
Anand Subramanian Puca Huachi Vaz Penna Eduardo Uchoa Luiz Satoru Ochi 《European Journal of Operational Research》2012
This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported. 相似文献
6.
The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are measured in terms of a given arc distance, the Cumulative Vehicle Routing Problem (CmVRP) is a variant of the problem that aims to minimize total energy consumption. Each arc’s energy consumption is defined as the product of the arc distance by the weight accumulated since the beginning of the route.The purpose of this work is to propose several different formulations for the CmVRP and to study their Linear Programming (LP) relaxations. In particular, the goal is to study formulations based on combining an arc-item concept (that keeps track of whether a given customer has already been visited when traversing a specific arc) with another formulation from the recent literature, the Arc-Load formulation (that determines how much load goes through an arc).Both formulations have been studied independently before – the Arc-Item is very similar to a multi-commodity-flow formulation in Letchford and Salazar-González (2015) and the Arc-Load formulation has been studied in Fukasawa et al. (2016) – and their LP relaxations are incomparable. Nonetheless, we show that a formulation combining the two (called Arc-Item-Load) may lead to a significantly stronger LP relaxation, thereby indicating that the two formulations capture complementary aspects of the problem. In addition, we study how set partitioning based formulations can be combined with these formulations. We present computational experiments on several well-known benchmark instances that highlight the advantages and drawbacks of the LP relaxation of each formulation and point to potential avenues of future research. 相似文献
7.
A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows 总被引:6,自引:0,他引:6
Michael Polacek Richard F. Hartl Karl Doerner Marc Reimann 《Journal of Heuristics》2004,10(6):613-627
The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times. 相似文献
8.
In this paper we deal with a generalization of the Vehicle Routing Problem with Time Windows that considers time-dependent travel times and costs. Through several steps we transform this extension into an Asymmetric Capacitated Vehicle Routing Problem, so it can be solved both optimally and heuristically with known codes. 相似文献
9.
The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits
certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it
is capable of providing very strong lower bounds and, in most cases, optimal solutions.
Received: November 1998 / Accepted: September 2000?Published online March 22, 2001 相似文献
10.
Emmanouil E. Zachariadis Christos D. Tarantilis Christos T. Kiranoudis 《European Journal of Operational Research》2009
We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions. 相似文献
11.
Phuong Khanh Nguyen Teodor Gabriel Crainic Michel Toulouse 《European Journal of Operational Research》2013
We propose a tabu search meta-heuristic for the Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows. Two types of neighborhoods, corresponding to the two sets of decisions of the problem, together with a strategy controlling the selection of the neighborhood type for particular phases of the search, provide the means to set up and combine exploration and exploitation capabilities for the search. A diversification strategy, guided by an elite solution set and a frequency-based memory, is also used to drive the search to potentially unexplored good regions and, hopefully, enhance the solution quality. Extensive numerical experiments and comparisons with the literature show that the proposed tabu search yields very high quality solutions, improving those currently published. 相似文献
12.
The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem. It deals with route planning and the distribution of goods from a depot to geographically dispersed customers by a fleet of vehicles with constrained capacities. The customers’ demands are known and each customer has a time window in which it has to be supplied. The time windows are assumed to be soft, that means, violations of the time windows are allowed, but associated with penalties. The problem is to organize the vehicle routes optimally, i.e. to minimize the total costs, consisting of the number of used vehicles and the total distance, and the penalties simultaneously. Thus, the problem is formulated as a bicriterion minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs. 相似文献
13.
Summary In this paper the Vehicle Routing-Allocation Problem (VRAP) is presented. In VRAP not all customers need be visited by the
vehicles. However customers not visited either have to be allocated to some customer on one of the vehicle tours or left isolated.
We concentrate our discussion on the Single Vehicle Routing-Allocation Problem (SVRAP). An integer linear programming formulation
of SVRAP is presented and we show how SVRAP provides a unifying framework for understanding a number of the papers and problems
presented in the literature.
Specifically the covering tour problem, the covering salesman problem, the median tour problem, the maximal covering tour
problem, the travelling salesman problem, the generalised travelling salesman problem, the selective travelling salesman problem,
the prize collecting travelling salesman problem, the maximum covering/shortest path problem, the maximum population/shortest
path problem, the shortest covering path problem, the median shortest path problem, the minimum covering/shortest path problem
and the hierarchical network design problem are special cases/variants of SVRAP. 相似文献
14.
提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少. 相似文献
15.
n this paper, we propose a reformulation and a Branch-and-price (BP) algorithm for the Vehicle Routing Problem with Cross-Docking (VRPCD). Our computational results indicate that the reformulation provides bounds much stronger than network flow bounds from previous studies. As a consequence, when BP and a Linear Programming based Branch-and-bound (LPBB) method (that relies on the network flow formulation) are run for the same restricted time limit, BP clearly dominates LPBB in terms of the quality of lower and upper bounds found during the search. 相似文献
16.
Iris Abril Martínez-Salazar Julian Molina Francisco Ángel-Bello Trinidad Gómez Rafael Caballero 《European Journal of Operational Research》2014
In this work we consider a Transportation Location Routing Problem (TLRP) that can be seen as an extension of the two stage Location Routing Problem, in which the first stage corresponds to a transportation problem with truck capacity. Two objectives are considered in this research, reduction of distribution cost and balance of workloads for drivers in the routing stage. Here, we present a mathematical formulation for the bi-objective TLRP and propose a new representation for the TLRP based on priorities. This representation lets us manage the problem easily and reduces the computational effort, plus, it is suitable to be used with both local search based and evolutionary approaches. In order to demonstrate its efficiency, it was implemented in two metaheuristic solution algorithms based on the Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization (SSPMO) and on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) strategies. Computational experiments showed efficient results in solution quality and computing time. 相似文献
17.
车辆路径问题的改进遗传算法 总被引:1,自引:0,他引:1
提出一种基于遗传算法的求解车辆路径问题的新算法,避免传统遗传算法处理不可行约束条件中惩罚项系数选取不当所出现的问题.同时,通过现实例子分析该算法的优劣性,实验结果表明该算法是一种有效的算法. 相似文献
18.
Gabriel Gutiérrez-Jarpa Guy Desaulniers Gilbert Laporte Vladimir Marianov 《European Journal of Operational Research》2010
In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers. 相似文献
19.