•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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
•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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
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.
Full text
Available for:
CEKLJ, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
•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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, 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.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
This paper is a survey of the literature on applications of evolutionary algorithms for vehicle routing problems. It reports on genetic algorithms, evolution strategies, and particle swarm ...optimization when applied to the classical capacitated vehicle routing problem and many of its variants. The performance of evolutionary algorithms is also compared with the best alternative problem-solving approaches on benchmark instances.
Full text
Available for:
CEKLJ, DOBA, IZUM, KILJ, NUK, ODKLJ, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
PDF
