共查询到20条相似文献,搜索用时 703 毫秒
1.
Tom Van Woensel Laoucine Kerbache Herbert Peremans Nico Vandaele 《Journal of Mathematical Modelling and Algorithms》2007,6(1):151-173
Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications
dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature
of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion
is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative
modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected
travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra
complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating
costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness
of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested
traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability
(obtained via the queueing approach) is quantified for the different datasets.
相似文献
2.
This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems. 相似文献
3.
In this paper, we investigate how robust and flexible solutions of a number of stochastic variants of the capacitated vehicle
routing problem can be obtained. To this end, we develop and discuss a method that combines a sampling based approach to estimate
the robustness or flexibility of a solution with a metaheuristic optimization technique. This combination allows us to solve
larger problems with more complex stochastic structures than traditional methods based on stochastic programming. It is also
more flexible in the sense that adaptation of the approach to more complex problems can be easily done. We explicitly recognize
the fact that the decision maker’s risk preference should be taken into account when choosing a robust or flexible solution
and show how this can be done using our approach. 相似文献
4.
Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks. 相似文献
5.
A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows 总被引:1,自引:0,他引:1
D. C. Paraskevopoulos P. P. Repoussis C. D. Tarantilis G. Ioannou G. P. Prastacos 《Journal of Heuristics》2008,14(5):425-455
This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective
is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both
the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The
problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable
Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions,
illustrating the effectiveness of the approach and its applicability to realistic routing problems.
This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under
contract GSRT NM-67. 相似文献
6.
Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. In practice, however, temporary traffic congestion make such solutions non-optimal with respect to minimizing the total duty time. Furthermore, the VRPTW does not account for driving hours regulations, which restrict the available travel time for truck drivers. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing of a VRPTW. We propose an ILP formulation that minimizes the total duty time. The results of a case study indicate that duty time reductions of 15% can be achieved. Furthermore, computational experiments on VRPTW benchmarks indicate that ignoring traffic congestion or driving hours regulations leads to practically infeasible solutions. Therefore, new vehicle routing methods should be developed that account for these common restrictions. We propose an integrated approach based on classical insertion heuristics. 相似文献
7.
Probabilistic diversification and intensification in local search for vehicle routing 总被引:18,自引:0,他引:18
This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving
vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches.
It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this
technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented
in this article, too. The solutions of nearly forty problem instances of the literature have been improved. 相似文献
8.
Jan Fabian Ehmke Ann Melissa Campbell Timothy L. Urban 《European Journal of Operational Research》2015
In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings. 相似文献
9.
This paper discusses neighborhood search algorithms where the size of the neighborhood is “very large” with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search
technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way
of creating and searching CIM neighborhoods for routing problems with side constraints. For such problems, the exact search
of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods
heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows
that CIM algorithms are very competitive approaches for solving vehicle routing problems. Overall, the solutions generated
by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from
the best-known solutions for large-scale capacitated VRP instances. 相似文献
10.
In this study, we formulate and analyze a strategic design model for three-echelon distribution systems with two-level routing
considerations. The key design decisions considered are: the number and locations of distribution centers (DC’s), which big
clients (clients with larger demand) should be included in the first level routing (the routing between plants and DC’s),
the first-level routing between plants, DC’s and big clients, and the second-level routing between DC’s and other clients
not included in the first-level routing. A hybrid genetic algorithm embedded with a routing heuristic is developed to efficiently
find near-optimal solutions. The quality of the solution to a series of small test problems is evaluated—by comparison with
the optimal solution solved using LINGO 9.0. In test problems for which exact solutions are available, the heuristic solution
is within 1% of optimal. At last, the model is applied to design a national finished goods distribution system for a Taiwan
label-stock manufacturer. Through the case study, we find that the inclusion of big clients in the first-level routing in
the analysis leads to a better network design in terms of total logistic costs. 相似文献
11.
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. 相似文献
12.
Kenneth Sörensen 《Journal of Heuristics》2007,13(1):35-47
In this paper, we discuss distance measures for a number of different combinatorial optimization problems of which the solutions
are best represented as permutations of items, sometimes composed of several permutation (sub)sets. The problems discussed
include single-machine and multiple-machine scheduling problems, the traveling salesman problem, vehicle routing problems,
and many others. Each of these problems requires a different distance measure that takes the specific properties of the representation
into account. The distance measures discussed in this paper are based on a general distance measure for string comparison
called the edit distance. We introduce several extensions to the simple edit distance, that can be used when a solution cannot
be represented as a simple permutation, and develop algorithms to calculate them efficiently. 相似文献
13.
研究了基于低碳排放的锦州JS配送公司的车辆路径优化问题.首先通过分析目前锦州JS配送公司的车辆路径规划方案发现该公司在规划路径时只关注路径最短,而忽视了碳排放成本.然后通过具体分析配送过程中能源消耗的来源,考虑车辆自重和载重、车辆出行距离等对配送能源消耗的影响,建立了以极小化碳排放成本为目标的车辆路径优化问题的混合整数规划模型,通过求解模型得到新的配送路径优化方案.优化后的配送方案比原先的配送方案减少了14.16万元的碳排放成本.研究结果对物流企业降低碳排放具有指导意义. 相似文献
14.
In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consideration. The optimal solution of the problem is computed using the proposed formulation, resulting in a saving of up to 28.6% in total travelling cost as compared to the current implementation. 相似文献
15.
The Skill Vehicle Routing Problem (Skill VRP) considers vehicle routing under the assumption of skill requirements given on demand nodes. These requirements have to be met by the serving vehicles. No further constraints, like capacity or cost restrictions, are imposed. Skill VRP solutions may show a tendency to have a bad load balancing and resource utilization. In a majority of solutions only a subset of vehicles is active. Moreover, a considerable share of demand nodes is served by vehicles that have a skill higher than necessary. A reason for that solution behavior lies in the model itself. As no resource restrictions are imposed, the Skill VRP tends to produce TSP-like solutions. To obtain better balanced solutions, we introduce two new approaches. First we propose a minmax model that aims at minimizing the maximal vehicle tour length. Second we suggest a two-step method combining the minmax approach with a distance constrained model. Our experiments illustrate that these approaches lead to improvements in load balancing and resource utilization, but, with different impact on routing costs. 相似文献
16.
The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and
(2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal
solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among
others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective
genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54
test instances from the TSPLIB are reported. 相似文献
17.
The vehicle routing problem with backhaul (VRPB) is an extension of the capacitated vehicle routing problem (CVRP). In VRPB, there are linehaul as well as backhaul customers. The number of vehicles is considered to be fixed and deliveries for linehaul customers must be made before any pickups from backhaul customers. The objective is to design routes for the vehicles so that the total distance traveled is minimized. We use multi-ant colony system (MACS) to solve VRPB which is a combinatorial optimization problem. Ant colony system (ACS) is an algorithmic approach inspired by foraging behavior of real ants. Artificial ants are used to construct a solution by using pheromone information from previously generated solutions. The proposed MACS algorithm uses a new construction rule as well as two multi-route local search schemes. An extensive numerical experiment is performed on benchmark problems available in the literature. 相似文献
18.
A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The variation is caused by congestion that is typically greatest during morning and evening rush hours. The algorithm is used to schedule a fleet of delivery vehicles operating in the South West of the United Kingdom for a sample of days. The results demonstrate how conventional methods that do not take time-varying speeds into account when planning, except for an overall contingency allowance, may still lead to some routes taking too long. The results are analysed to show that in the case study using the proposed approach can lead to savings in CO2 emissions of about 7%. 相似文献
19.
《European Journal of Operational Research》2006,169(2):606-622
In this paper we use a scatter search framework to solve the vehicle routing problem with time windows (VRPTW). Our objective is to achieve effective solutions and to investigate the effects of reference set design parameters pertaining to size, quality and diversity. Both a common arc method and an optimization-based set covering model are used to combine vehicle routing solutions. A reactive tabu search metaheuristic and a tabu search with an advanced recovery feature, together with a set covering procedure are used for solution improvement. Our approach led to a robust solution method, generating solution quality that is competitive with the current best metaheuristics. 相似文献
20.
We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach. 相似文献