Vehicle Problem Routing (VPR)

mayo 12, 2010

Intro

The Vehicle Routing Problem (VRP) is one of the most challenging combinatorial optimization tasks. Defined long time ago, this problem consists in designing the optimal set of routes for fleet of vehicles in order to serve a given set of customers. The interest in VRP is motivated by its practical relevance as well as by its considerable difficulty.

The Vehicle Routing Problem (VRP) is a generic name given to a whole class of problems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number of geographically dispersed cities or customers. The objective of the VRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot

The VRP is a well known integer programming problem which falls into the category of NP Hard (Non-deterministic Polynomial-time Hard) problems, meaning that the computational effort required to solve this problem increases exponentially with the problem size. For such problems it is often desirable to obtain approximate solutions, so they can be found fast enough and are sufficiently accurate for the purpose. Usually this task is accomplished by using various heuristic methods, which rely on some insight into the problem nature.

This difficult combinatorial problem conceptually lies at the intersection of these two well-studied problems:

  • The Traveling Salesman Problem (TSP): If the capacity of the vehicles C is infinite, we can get an instance of the Multiple Traveling Salesman Problem (MTSP). An MTSP instance can be transformed into an equivalent TSP instance by adjoining to the graph k-1 (being k the number of routes) additional copies of node 0 and its incident edges (there are no edges among the k depot nodes).
  • The Bin Packing Problem (BPP): The question of whether there exists a feasible solution for a given instance of the VRP is an instance of the BPP. The decision version of this problem is conceptually equivalent to a VRP model in which all edge costs are taken to be zero (so that all feasible solutions have the same cost).

Hence, we can think of the first transformation as relaxing the underlying packing (BPP) structure and the second transformation as relaxing the underlying routing (TSP) structure. A feasible solution to the full problem is a TSP tour (in the expanded graph) that also satisfies the packing constraints (i.e., the total demand along each of the k segments joining successive copies of the depot does not exceed C). Because of the interplay between the two underlying models (both of them are NP Hard problems), instances of the Vehicle Routing Problem can be extremely difficult to solve in practice.

The VRP arises naturally  as a central problem in the fields of transportation, distribution and logistics. In some market sectors, transportation means a high percentage of the value added to goods. Therefore, the utilization of computerized methods for transportation often results in significant savings ranging from 5% to 20% in the total costs. Usually, in real world VRPs, many side constraints appear.

Below, it’s described different variants in VRP cases:

1-Capacitated VRP (CPRV)

CVRP is a Vehicle Routing Problem  in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. That is, CVRP is like VRP with the additional constraint that every vehicle must have uniform capacity of a single commodity.

We can find below a formal description for the CVRP:

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time, and the total demand of commodities for each route may not exceed the capacity of the vehicle which serves that route.
  • Feasibility: A solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route.

2. Multiple Depot VRP (MDVRP)

A company may have several depots from which it can serve its customers. If the customers are clustered around depots, then the distribution problem should be modeled as a set of independent VRPs. However, if the customers and the depots are intermingled then a Multi-Depot Vehicle Routing Problem should be solved.

A MDVRP requires the assignment of customers to depots. A fleet of vehicles is based at each depot. Each vehicle originate from one depot, service the customers assigned to that depot, and return to the same depot.

The objective of the problem is to service all customers while minimizing the number of vehicles and travel distance.

We can find below a formal description for the MDVRP:

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time, and the total demand of commodities must be served from several depots.
  • Feasibility: A solution is feasible if each route satisfies the standard VRP constraints and begins and ends at the same depot.

3. Periodic VRP (PVRP)

In classical VRPs, typically the planning period is a single day. In the case of the Period Vehicle Routing Problem (PVRP), the classical VRP is generalized by extending the planning period to M days.

We define the problem as follows:

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.
  • Feasibility: A solution is feasible if all constraints of VRP are satisfied. Furthermore a vehicle may not return to the depot in the same day it departs. Over the M-day period, each customer must be visited at least once.

4. Split Delivery VRP (SDVRP)

SDVRP is a relaxation of the VRP wherein it is allowed that the same customer can be served by different vehicles if it reduces overall costs. This relaxation is very important if the sizes of the customer orders are as big as the capacity of a vehicle.

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.
  • Feasibility: A solution is feasible if all constraints of VRP are satisfied except that a customer may be supplied by more than one vehicle.

5-Stochastic VRP (SVRP)

Stochastic VRP (SVRP) are VRPs where one or several components of the problem are random. Three different kinds of SVRP are the next examples:

  • Stochastic customers: Each customer X is present with probability Y and absent with probability 1-Y.
  • Stochastic demands: The demand d of each customer is a random variable.
  • Stochastic times: Service times  and travel times  are random variables.

In SVRP, two stages are made for getting a solution. A first solution is determined before knowing the realizations of the random variables. In a second stage, a recourse or corrective action can be taken when the values of the random variables are known.

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers with random values on each execution for the customers to be served, their demands and/or the service and travel times.
  • Feasibility: When some data are random, it is no longer possible to require that all constraints be satisfied for all realizations of the random variables. So the decision maker may either require the satisfaction of some constraints with a given probability, or the incorporation into the model of corrective actions to be taken when a constraint is violated.

5-VRP with Backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is a VRP in which customers can demand or return some commodities. So in VRPPD it’s needed to take into account that the goods that customers return to the deliver vehicle must fit into it. The critical assumption in that all deliveries must be made on each route before any pickups can be made. This arises from the fact that the vehicles are rear-loaded, and rearrangement of the loads on the tracks at the delivery points is not deemed economical or feasible. The quantities to be delivered and picked-up are fixed and known in advance. VRPB is similar to VRPPD with the restriction that in the case of VRPB all deliveries for each route must be completed before any pickups are made.

  • Objective: The objective is to find such a set of routes that minimizes the total distance traveled.
  • Feasibility: A feasible solution of the problem consists of a set of routes where all deliveries for each route are completed before any pickups are made and the vehicle capacity is not violated by either the linehaul or backhaul points assigned to the route.

6-VRP with Pick-Up and Delivering

The Vehicle Routing Problem with Pick-up and Delivering (VRPPD) is a VRP in which the possibility that customers return some commodities is contemplated. So in VRPPD it’s needed to take into account that the goods that customers return to the deliver vehicle must fit into it. This restriction make the planning problem more difficult and can lead to bad utilization of the vehicles capacities, increased travel distances or a need for more vehicles.

Hence, it is usually to consider restricted situations where all delivery demands start from the depot and all pick-up demands shall be brought back to the depot, so there are no interchanges of goods between the customers. Another alternative is relaxing the restriction that all customers have to be visited exactly once. Another usual simplification is to consider that every vehicle must deliver all the commodities before picking up any goods.

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time, with the restriction that the vehicle must have enough capacity for transporting the commodities to be delivered and those ones picked-up at customers for returning them to the depot.
  • Feasibility: A solution is feasible if the the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route and the vehicle has enough capacity for picking-up the commodities at customers.

7-VRP with Satellite Facilities

An important aspect of the vehicle routing problem (VRP) that has been largely overlooked is the use of satellite facilities to replenish vehicles during a route. When possible, satellite replenishment allows the drivers to continue making deliveries until the close of their shift without necessarily returning to the central depot. This situation arises primarily in the distribution of fuels and certain retail items.

8-VRP with Time Windows (VRPTW)

The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer v belongs to V, defining an interval (eo,l0) wherein the customer has to be supplied. The interval (eo,l0) at the depot is called the scheduling horizon. Here is a formal description of the problem:

  • Objective: The objective is to minimize the vehicle fleet and the sum of travel time and waiting time needed to supply all customers in their required hours.
  • Feasibility: The VRPTW is, regarding to VRP, characterized by the following additional restrictions:
    • A solution becomes infeasible if a customer is supplied after the upper bound of its time window.
    • A vehicle arriving before the lower limit of the time window causes additional waiting time on the route.
    • Each route must start and end within the time window associated with the depot.
    • In the case of soft time widows, a later service does not affect the feasibility of the solution, but is penalized by adding a value to the objective function.

Solution techniques

the most commonly used techniques for solving Vehicle Routing Problems are listed. Near all of them are heuristics and metaheuristics because no exact algorithm can be guaranteed to find optimal tours within reasonable computing time when the number of cities is large. This is due to the NP-Hardness of the problem. Next we can find a classification of the solution techniques we have considered:

  • Exact Approaches: As the name suggests, this approach proposes to compute every possible solution until one of the bests is reached.
  • Heuristics: Heuristic methods perform a relatively limited exploration of the search space and typically produce good quality solutions within modest computing times.
    • Constructive Methods: Gradually build a feasible solution while keeping an eye on solution cost, but do not contain an improvement phase per se.
    • 2-Phase Algorithm: The problem is decomposed into its two natural components:
        1. Clustering of vertices into feasible routes
        2. Actual route construction
  • Meta-Heuristics: In metaheuristics, the emphasis is on performing a deep exploration of the most promising regions of the solution space. The quality of solutions produced by these methods is much higher than that obtained by classical heuristics.

Sofwares.

It exist different companies, which have developed softwares  to get a solution for this problem. Many firms spend a lot money and time to find the best option for their service.

Caliper develop three main different software services:

  • Transcad: is the first and only Geographic Information System (GIS) designed specifically for use by transportation professionals to store, display, manage, and analyze transportation data. TransCAD combines GIS and transportation modeling capabilities in a single integrated platform, providing capabilities that are unmatched by any other package. TransCAD can be used for all modes of transportation, at any scale or level of detail. TransCAD provides:
    • A powerful GIS engine with special extensions for transportation
    • Mapping, visualization, and analysis tools designed for transportation applications
    • Application modules for routing, travel demand forecasting, public transit, logistics, site location, and territory management
  • TransModeler: TransModeler is a powerful and versatile traffic simulation package applicable to a wide array of traffic planning and modeling tasks. TransModeler can simulate all kinds of road networks, from freeways to downtown areas, and can analyze wide area multimodal networks in great detail and with high fidelity. You can model and visualize the behavior of complex traffic systems in a 2-dimensional or 3-dimensional GIS environment to illustrate and evaluate traffic flow dynamics, traffic signal and ITS operations, and overall network performance.TransModeler breaks new ground in ease-of-use for complex simulation applications and integrates with TransCAD, the most popular travel demand forecasting software in the U.S., to provide a complete solution for evaluating the traffic impacts of future planning scenarios. Moreover, the TransModeler mapping, simulation, and animation tools allow you to present study findings to decision-makers in a clear and compelling fashion

  • Maptitude Mapping Software: Maptitude Geographic Information System (GIS) software is the intelligent mapping solution for business, government, and education. Maptitude is a powerful combination of software and geographic data that provides everything you need to realize the benefits of desktop mapping and spatial analysis with a single, easy-to-use package. With Maptitude you can:
    • Create beautiful, informative map displays
    • Enhance reports and presentations with maps that clearly illustrate your message
    • Find geographic patterns that cannot be seen in database tables and spreadsheets
    • Answer geographic questions that impact your operations
    • Share geographic data with your workgroup, department, or organization

AIMMS is an advanced development environment for building optimization based operations research applications and advanced planning systems. It is used by leading companies to support decision making in a wide range of industries in areas such as supply chain management, production planning, logistics, forestry planning and risk-, revenue- and asset- management.

This company has services of  Support, Consulting, workshops, webmeetings, documentation… and it works in different areas of industries, between them, logistics and manufacturing

Win Route  software leverages advanced planning and optimization technologies and was designed in particularly strong interaction with dispatchers, transport managers and study departments. That is why no other solution will match your needs and integrate into your company better than Win Route.

Win Route can calculate your daily planning (operational mode). It can as well examine the cost-effectiveness of your transport strategy (study mode). Win Route helps you understand and control your company transportation cost thereby ensuring you stay ahead of competition.

Slogan: They will keep investing in math and cloud computing with the final goal to support a green economy of mobility. In other words, they want to reduce the operating expenses and boost business of our customers while reducing the social costs generated by their need to move people, food and all other goods. The company conceive our models to fully exploit the growing mass connectivity and mass computational power.

The efficient methods consider only the most reasonable routes. These approaches are called heuristics and require a model of intelligence as a selection criterion. Effective are those heuristics which mimic the nature: have you ever noticed that a line of ants soon bypasses any obstacle via the shortest path around it? Also genetics may play a good reference for heuristics: selecting and merging cheap couples of routes frequently happens to generate increasingly cheaper routes for further coupling till the best route is generated. Smart selection criteria speed up this calculus and enable dynamic applications.

Services: Route optimization in case of:

  • pickup and delivery applications
  • multiple vehicles with limited capacity
  • management of desired/required time windows
  • Management of fixed and variable appointments

Solutions for:

  • Asymmetryc TSP (Traveler Sales Man problem) and VRP (Vehicle Route Problem)
  • Multi-vehicle optimal and load-balanced assignements
  • Solver of routing problems up to thousands of destionations and vehicles
  • Solver of Time Windowed VRP routing problems
  • Solver of multi-dimensional knapsack geographical problems
  • Solver of PickUp&Delivery time windowed problems
  • Integration of optimal tour deliveries (to drivers’ navigators, driving direction, email, list of addresses, …)
  • M2M middleware integration to update the address demand in real time
  • Validation and control via GPS tracking
  • Geofencing; adaptive, self learning and increasingly accurate scheduling of planned tours

Demo case: http://www.youtube.com/watch?v=Whoeq91FDys

Cases:

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: