•A vehicle routing problem with time-dependent travel times is addressed.•Time dependency is accounted for in each road segment of a network.•The path to go from one customer to the next in the road ...network is time-dependent.•A tabu search is proposed to solve the problem.•A dominant shortest path structure is used to speed up the computations.
Travel times inside cities often vary quite a lot during a day and significantly impact the duration of commercial delivery routes. Several authors have suggested time-dependent variants of the most commonly encountered vehicle routing problems. In these papers, however, time-dependency is usually defined on customer-based graphs. Thus, one major impact of travel time variations is missed: in an urban environment, not only do travel times change, but also the paths used to travel from one customer to another. In fact, during a day, different paths may be used at different points in time. To address this issue, one possible approach is to work directly with the road network and consider travel time (or travel speed) variations on each road segment.
In this paper, we propose a solution approach for a time-dependent vehicle routing problem with time windows in which travel speeds are associated with road segments in the road network. This solution approach involves a tabu search heuristic that considers different shortest paths between any two customers at different times of the day. A major contribution of this work is the development of techniques to evaluate the feasibility and the approximate cost of a solution in constant time, which allows the solution approach to handle problem instances with up to 200 nodes and 580 arcs in very reasonable computing times. The performance of our algorithm is assessed by comparing it to an exact method on a set of benchmark instances. The results show that solutions of high quality are produced.
•A technician routing and scheduling problem is solved with a tabu search-based metaheuristic.•The problem has specific features like parts inventory and multiple time windows.•The tabu search uses ...an adaptive memory that accounts for solution quality and diversity.•Results are reported on problem instances with up to 200 tasks.•A comparison with a branch-and-price algorithm is reported on small instances.
This paper addresses a technician routing and scheduling problem motivated by an application for the repair and maintenance of electronic transactions equipment. The problem exhibits many special features like multiple time windows for service, an inventory of spare parts carried by each technician and tasks that may require a special part to be performed. A problem-solving methodology based on tabu search, coupled with an adaptive memory, is proposed. The inclusion of solutions (local minima) in the adaptive memory takes into account both quality and diversity. Results are reported on test instances with up to 200 tasks. A comparison with a previously developed branch-and-price algorithm is also reported on instances of small size.
The vehicle routing problem with multiple routes consists in determining the routing of a fleet of vehicles when each vehicle can perform multiple routes during its operations day. This problem is ...relevant in applications where the duration of each route is limited, for example when perishable goods are transported. In this work, we assume that a fixed-size fleet of vehicles is available and that it might not be possible to serve all customer requests, due to time constraints. Accordingly, the objective is first to maximize the number of served customers and then, to minimize the total distance traveled by the vehicles. An adaptive large neighborhood search, exploiting the ruin-and-recreate principle, is proposed for solving this problem. The various destruction and reconstruction operators take advantage of the hierarchical nature of the problem by working either at the customer, route or workday level. Computational results on Euclidean instances, derived from well-known benchmark instances, demonstrate the benefits of this multi-level approach.
The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict ...time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.
This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed ...methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.
•A delivery problem with synchronization constraints among vehicles is addressed with an adaptive large neighborhood search.•The reinsertion operator exploits the constraint propagation capabilities ...of constraint programming to guarantee feasibility.•Destruction operators specifically designed for our problem are introduced.•Results are reported on instances with up to 200 customers.
This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers.
Geographic information systems, global positioning systems, traffic flow sensors and cellular phones are sources of real-time traffic data in road networks. However, many vehicle routing algorithms ...do not account for this real-time information. In this paper, we consider the problem of adjusting in real-time a time-dependent delivery plan to respond to dynamic changes in travel times. We also consider a variant of the problem in which some customer requests can be canceled. The goal is to minimize disruption by maintaining as much as possible the current planned routes, although without compromising too much solution quality. Computational results obtained by solving instances with up to 500 customers are reported and compared with a strategy that maintains the planned routes, whatever the cost.
•A vehicle routing problem is defined in a real urban road network.•The travel times are time-dependent and are derived from real historical data.•Dynamic perturbations to the time-dependent travel times are accounted for.•The proposed methodology adjusts the routing plan when dynamic perturbations occur.•Both solution stability and solution quality are taken into account.
This paper describes an exact
ϵ
-constraint method for bi-objective combinatorial optimization problems with integer objective values. This method tackles multi-objective optimization problems by ...solving a series of single objective subproblems, where all but one objectives are transformed into constraints. We show in this paper that the Pareto front of bi-objective problems can be efficiently generated with the
ϵ
-constraint method. Furthermore, we describe heuristics based on information gathered from previous subproblems that significantly speed up the method. This approach is used to find the exact Pareto front of the Traveling Salesman Problem with Profits, a variant of the Traveling Salesman Problem in which a profit or prize value is associated with each vertex. The goal here is to visit a subset of vertices while addressing two conflicting objectives: maximize the collected prize and minimize the travel costs. We report the first exact results for this problem on instances derived from classical Vehicle Routing and Traveling Salesman Problem instances with up to 150 vertices. Results on approximations of the Pareto front obtained from a variant of our exact algorithm are also reported.
The traditional view of mysticete feeding involves static baleen directly sieving particles from seawater using a simple, dead-end flow-through filtration mechanism. Flow tank experiments on bowhead ...(Balaena mysticetus) baleen indicate the long-standing model of dead-end filtration, at least in balaenid (bowhead and right) whales, is not merely simplistic but wrong. To recreate continuous intraoral flow, sections of baleen were tested in a flume through which water and buoyant particles circulated with variable flow velocity. Kinematic sequences were analyzed to investigate movement and capture of particles by baleen plates and fringes. Results indicate that very few particles flow directly through the baleen rack; instead much water flows anteroposteriorly along the interior (lingual) side of the rack, allowing items to be carried posteriorly and accumulate at the posterior of the mouth where they might readily be swallowed. Since water flows mainly parallel to rather than directly through the filter, the cross-flow mechanism significantly reduces entrapment and tangling of minute items in baleen fringes, obviating the need to clean the filter. The absence of copepods or other prey found trapped in the baleen of necropsied right and bowhead whales supports this hypothesis. Reduced through-baleen flow was observed with and without boundaries modeling the tongue and lips, indicating that baleen itself is the main if not sole agent of crossflow. Preliminary investigation of baleen from balaenopterid whales that use intermittent filter feeding suggests that although the biomechanics and hydrodynamics of oral flow differ, cross-flow filtration may occur to some degree in all mysticetes.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
•We introduce a cooperative coevolutionary algorithm for the Multi-Depot VRP.•We propose an ES with variable length genotype coupled with local search operators.•The proposed approach produces ...high-quality solutions in low computational time.•The performance is not greatly affected by the overlap between subproblems.•The proposed method could find improved solutions in many instances.
The Multi-Depot Vehicle Routing Problem (MDVRP) is an important variant of the classical Vehicle Routing Problem (VRP), where the customers can be served from a number of depots. This paper introduces a cooperative coevolutionary algorithm to minimize the total route cost of the MDVRP. Coevolutionary algorithms are inspired by the simultaneous evolution process involving two or more species. In this approach, the problem is decomposed into smaller subproblems and individuals from different populations are combined to create a complete solution to the original problem. This paper presents a problem decomposition approach for the MDVRP in which each subproblem becomes a single depot VRP and evolves independently in its domain space. Customers are distributed among the depots based on their distance from the depots and their distance from their closest neighbor. A population is associated with each depot where the individuals represent partial solutions to the problem, that is, sets of routes over customers assigned to the corresponding depot. The fitness of a partial solution depends on its ability to cooperate with partial solutions from other populations to form a complete solution to the MDVRP. As the problem is decomposed and each part evolves separately, this approach is strongly suitable to parallel environments. Therefore, a parallel evolution strategy environment with a variable length genotype coupled with local search operators is proposed. A large number of experiments have been conducted to assess the performance of this approach. The results suggest that the proposed coevolutionary algorithm in a parallel environment is able to produce high-quality solutions to the MDVRP in low computational time.
PDF
