DanielaPonce's timewindows [26 articles]

Abstract

In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and ...

Abstract

This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with ...

Abstract

In this paper we apply the concept of parallel processing to enhance the performance of the Ant Colony System algorithm. New exchange strategies based on a weighting scheme are introduced under three different types of interactions. A search assessment technique based on a team consensus methodology is developed to study the influence of these strategies on the search behavior. This technique demonstrates the influence of these strategies in terms of search diversity. The performance of the Multiple Ant Colony System algorithm, ...

Abstract

This paper presents several Arcs-States models that can be applied to numerous vehicle routing problems, one of which is the well-known vehicle routing problem with capacities and time windows. In these models, the variables correspond to the states (i.e. the resource quantities) of the vehicles when they travel through an arc. The LP relaxation of the problem provides a lower bound that can be embedded in a branch and bound algorithm that solves the problem exactly. However, for the pseudo-polynomial number ...

Abstract

This paper describes an exact algorithm for solving a problem where the same vehicle performs several routes to serve a set of customers with time windows. The motivation comes from the home delivery of perishable goods, where vehicle routes are short and must be combined to form a working day. A method based on an elementary shortest path algorithm with resource constraints is proposed to solve this problem. The method is divided into two phases: in the first phase, all non-dominated ...

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because ...

Abstract

This paper presents a tabu search metaheuristic to aid in the coordination and synchronization of the production and delivery of multi-product newspapers to bulk delivery locations. The problem is modeled as an open vehicle routing problem with time windows and zoning constraints. The methodology is applied to the newspaper production and distribution problem in a major metropolitan area. Computational results are presented and show significant improvement relative to an existing newspaper company's operations. ...

Abstract

This paper studies approximations to the average length of vehicle routing problems (VRP) with time window, route duration, and capacity constraints. The approximations are valuable for the strategic and planning analysis of transportation and logistics problems. Using asymptotic properties of vehicle routing problems and the average probability of successfully sequencing a customer with time windows a new expression to estimate VRP distances is developed. The increase in the number of routes when time constraints are added is modeled probabilistically. This paper ...

Abstract

Hot rolling scheduling is a difficult problem in the steel processing industry. It involves many objectives and constraints in both technical and practical respects. A two-stage scheduling method is proposed in this paper. Batch planning of staple material is formulated as a VRPTW, which is solved with a modified PGA. Then, batches of the established units are optimized by adjusting rolling sequences using intelligent search algorithms to reach higher hot charge ratios. This method has been applied to a hot strip ...

Abstract

One of the major research topics in the supply chain management field is the multi-depot vehicle routing problem with time windows (m-VRPTW). It aims to designing a set of minimum-cost routes for a vehicle fleet servicing many customers with known demands and predefined time windows. This paper presents an m-VRPTW local search improvement algorithm that explores a large neighborhood of the current solution to discover a cheaper set of feasible routes. The neighborhood structure comprises all solutions that can be generated ...

Abstract

This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are ...

Abstract

In this paper, we address a real life waste collection vehicle routing problem with time windows (VRPTW) with consideration of multiple disposal trips and drivers’ lunch breaks. Solomon's well-known insertion algorithm is extended for the problem. While minimizing the number of vehicles and total traveling time is the major objective of vehicle routing problems in the literature, here we also consider the route compactness and workload balancing of a solution since they are very important aspects in practical applications. In order ...

Abstract

The classical vehicle routing problem involves designing a set of routes for a fleet of vehicles based at one central depot that is required to serve a number of geographically dispersed customers, while minimizing the total travel distance or the total distribution cost. Each route originates and terminates at the central depot and customers demands are known. In many practical distribution problems, besides a hard time window associated with each customer, defining a time interval in which the customer should be ...

Abstract

We generalize the standard vehicle routing problem with time windows by allowing both traveling times and traveling costs to be time-dependent functions. In our algorithm, we use a local search to determine routes of the vehicles. When we evaluate a neighborhood solution, we must compute an optimal time schedule for each route. We show that this subproblem can be efficiently solved by dynamic programming, which is incorporated in the local search algorithm. The neighborhood of our local search consists of slight ...

Abstract

In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the ...

Abstract

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. ...

Abstract

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams ( m -MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must ...

Abstract

We consider an extension of the Split Delivery Vehicle Routing Problem, whereby customers may have a time window for their delivery. A construction heuristic is developed which uses a look-ahead approach to solve the Split Delivery Vehicle Scheduling Problem with Time Windows. Two improvement heuristics are also described: one attempts to move customers between routes, while the other exchanges customers between routes. All three heuristics are implemented on a specifically developed data set and on some standard problems from the literature. ...

Abstract

This paper presents a novel three-phase heuristic/algorithmic approach for the multi-depot routing problem with time windows and heterogeneous vehicles. It has been derived from embedding a heuristic-based clustering algorithm within a VRPTW optimization framework. To this purpose, a rigorous MILP mathematical model for the VRPTW problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 25 nodes to optimality. To overcome this limitation, a preprocessing stage clustering nodes together is initially performed ...

Abstract

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost ...

Abstract

In this paper, a vehicle routing problem with fuzzy time windows (VRPFTW) is proposed and solved. In the transportation business, time windows are not always strictly obeyed and the deviation of service time from the customer-specific time window determines the customer's satisfaction level, which can also be regarded as the supplier's service level. This paper applies fuzzy membership functions to characterize the service level issues associated with time window violation in a vehicle routing problem and proposes VRPFTW. VRPFTW is formulated ...

Abstract

An algorithm for the distribution of fresh vegetables in which the perishability represents a critical factor was developed. This particular problem was formulated as a vehicle routing problem with time windows and time-dependent travel-times (VRPTWTD) where the travel-times between two locations depends on both the distance and on the time of the day. The model considers the impact of the perishability as part of the overall distribution costs and a heuristic approach, based on the tabu search is used to solve ...

Abstract

We propose an iterated local search algorithm for the vehicle routing problem with time window constraints. We treat the time window constraint for each customer as a penalty function, and assume that it is convex and piecewise linear. Given an order of customers each vehicle to visit, dynamic programming (DP) is used to determine the optimal start time to serve the customers so that the total time penalty is minimized. This DP algorithm is then incorporated in the iterated local search ...

Abstract

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to ...

Abstract

This study has extended a vehicle routing problem, with time-windows (VRPTW), by considering the randomness of the perishable food delivery process, and constructing a SVRPTW model, to obtain optimal delivery routes, loads, fleet dispatching and departure times for delivering perishable food from a distribution center. Our objective was to minimize not only the fixed costs for dispatching vehicles, but also the transportation, inventory, energy and penalty costs for violating time-windows. We also discussed time-dependent travel and time-varying temperatures, during the day, ...

Abstract

This paper presents an efficient and well-scalable metaheuristic for fleet size and mix vehicle routing with time windows. The suggested solution method combines the strengths of well-known threshold accepting and guided local search metaheuristics to guide a set of four local search heuristics. The computational tests were done using the benchmarks of [Liu, F.-H., & Shen, S.-Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research Society, 50 (7), 721–732] and 600 ...