Vehicle Routing Problem (VRP) and Traveling Salesman Problem Types

In generic VRP, we have a number of orders (requests) to be carried out by a given set of vehicles. Each order (request) consists of picking up a quantity of goods or passengers at one location and delivering it to another location. The objective of the problem is to find a feasible set of routes for the vehicles so that all requests are serviced, and such that the overall cost or travel distance is minimized.

A feasible route of a vehicle must start at a given location, service a number of requests such that the capacity of the vehicle is not exceeded, and finally end at a given location.A pick-up or delivery must take place within a given time window. Each request has an associated pick-up precedence number, and a delivery precedence number. A vehicle must visit the locations in nondecreasing order of precedences. Since not all vehicles may be able to service all requests (e.g. due to their physical size or the absence of some cooling compartments) we need to ensure that every request is serviced by a given subset of vehicles. Between any two locations we have an associated, nonnegative distance and travel time.

There are types of VRPs which differ in some aspects. There are no standart or generally accepted naming for VRP types nor framework that categorize the VRP types. In literature, some studies exist that categorize the VRPs. A recent thorough survey is the study of Sophie N. Parragh, Karl F. Doerner and Richard F. Hartl [cf. Production & Operations Management web page of University of Wien]. This document is mainly based on this survey. Some VRP type naming in this document come from the study "A general heuristic for vehicle routing problems" of David Pisinger and Stefan Ropke [cf. Online paper on ACM Portal].

Vehicle Routing Problem with Clustered Backhauls (VRPCB)


Vehicle Count: Multi Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: All linehauls (deliveries) before backhauls (pick-ups)

Customer Type Restriction: Linehaul (delivery) customer or backhaul (pick-up) customer, but not both. The customers can be either a customer only requiring deliveries, or a customer only requiring pick-ups.

Good Restriction: There is no restriction on goods to be carried.

Description: This type is characterized by the requirement that the group or cluster of delivery customers has to be served before the first pick-up customer can be visited. Delivery customers are also denoted as linehaul customers, pick-up customers as backhaul customers. In the literature this problem class is denoted as Vehicle Routing Problem (VRP) with Backhauls.

Traveling Salesman Problem (TSP) with Clustered Backhauls (TSPCB)


Vehicle Count: Single Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: All linehauls (deliveries) before backhauls (pick-ups)

Customer Type Restriction: Linehaul (delivery) customer or backhaul (pick-up) customer, but not both. The customers can be either a customer only requiring deliveries, or a customer only requiring pick-ups.

Good Restriction: There is no restriction on goods to be carried.

Description:

Single vehicle case of VRPCB

VRP with Mixed linehauls and Backhauls (VRPMB)


Vehicle Count: Multi Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: No restriction (Mixed visiting of customers is allowed)

Customer Type Restriction: Linehaul (delivery) customer or backhaul (pick-up) customer, but not both. The customers can be either a customer only requiring deliveries, or a customer only requiring pick-ups.

Good Restriction: There is no restriction on goods to be carried.

Description:

Unlike VRPCB, mixed visiting sequences are explicitly allowed.

TSP with Mixed linehauls and Backhauls (TSPMB)


Vehicle Count: Single Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: No restriction (Mixed visiting is allowed)

Customer Type Restriction: Linehaul (delivery) customer or backhaul (pick-up) customer, but not both. The customers can be either a customer only requiring deliveries, or a customer only requiring pick-ups.

Good Restriction: There is no restriction on goods to be carried.

Description:

Single vehicle case of VRPMB

VRP with Divisible Delivery and Pick-up (VRPDDP)


Vehicle Count: Multi Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: Delivery first, visiting twice allowed. Visit to the station twice is allowed, but in the first visit delivery must be done.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be one at the customer.

Good Restriction: Linehaul (delivery) and backhaul (pick-up) quantity

Description:

The deliveries and pick-ups are divided. Rather, two visits, one for delivery and one for pick-up are possible. In this case, first a few customers are visited for delivery service only, in order to empty the vehicle partially. Then, customers are visited where goods are delivered and picked up. At the end, the pick-ups are performed for the customers initially visited for delivery. A customer can either be visited once for both pick-up and delivery or twice, first for delivery and then for pick-up.

TSP with Divisible Delivery and Pick-up (TSPDDP)


Vehicle Count: Single Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: Delivery first, visiting twice allowed. Visit to the station twice is allowed, but in the first visit delivery must be done.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be one at the customer.

Good Restriction: Linehaul (delivery) and backhaul (pick-up) quantity

Description:

Single vehicle case of VRPDDP

VRP with Simultaneous Delivery and Pick-up (VRPSDP)


Vehicle Count: Multi Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity

Description:

Every customer is associated with a linehaul (delivery) as well as a backhaul (pick-up) quantity. It is imposed that every customer can only be visited exactly once.

TSP with Simultaneous Delivery and Pick-up (TSPSDP)


Vehicle Count: Single Vehicle

Depot Count: Multi / Single Depot

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity

Description:

Single vehicle case of VRPSDP

Pick-up and Delivery Vehicle Routing Problem (PDVRP)


Vehicle Count: Multi Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: -

Customer Type Restriction: -

Good Restriction: Homogeneous goods

Description:

Refers to problems where goods are transported from pick-up to delivery points. The delivery and pick-up locations are not paired.

Pick-up and Delivery Traveling Salesman Problem (PDTSP)


Vehicle Count: Single Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: -

Customer Type Restriction: -

Good Restriction: Homogeneous goods

Description:

Single vehicle case of PDVRP

Pick-up and Delivery Problem (PDP)


Vehicle Count: Multi Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: No other customer can be visited between a pick-up and its associated delivery location.

Customer Type Restriction: -

Good Restriction: Goods

Description:

This type of problems consider transportation requests, each associated with an origin and a destination, resulting in paired pick-up and delivery points.

Single Pick-up and Delivery Problem (SPDP)


Vehicle Count: Single Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: No other customer can be visited between a pick-up and its associated delivery location.

Customer Type Restriction: -

Good Restriction: Goods

Description:

Single vehicle case of PDP

Dial-A-Ride Problem (DARP)


Vehicle Count: Multi Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: No other customer can be visited between a pick-up and its associated delivery location.

Customer Type Restriction: -

Good Restriction: Passengers, convenience, speed limitations, etc.

Description:

This type of problems consider transportation requests, each associated with an origin and a destination, resulting in paired pick-up and delivery points, but with the constraint that passengers are transported in contrast to PDP.

Single Dial-A-Ride Problem (SDARP)


Vehicle Count: Single Vehicle

Depot Count: No depot. Orders are between customers or some locations.

Visiting Restriction: No other customer can be visited between a pick-up and its associated delivery location.

Customer Type Restriction: -

Good Restriction: Passengers, convenience, speed limitations, etc.

Description:

Single vehicle case of DARP

Capacitated vehicle routing problem (CVRP)


Vehicle Count: Multi Vehicle

Depot Count: Single Depot.

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity.

Description:

A CVRP is a similar problem to VRP with simultaneous delivery and pick-up problems.

Open vehicle routing problem (OVRP)


Vehicle Count: Multi Vehicle

Depot Count: Single Depot.

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity.

Description:

The OVRP is very close to the CVRP. The difference between the two problems is that in the OVRP the vehicles do not have to return to the depot. Thus, an OVRP can be solved as an asymmetric CVRP by setting distances and travel times from every customer to the depot to zero.

Site-dependent vehicle routing problem (SDVRP)


Vehicle Count: Multi Vehicle

Depot Count: Single Depot.

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity.

Description:

SDVRP can be considered as a generalization of CVRP. In the SDVRP a customer may only be serviced by a given subset of the vehicles, typically because the access paths to the node do not allow given vehicles to pass, or because specific facilities are demanded in the vehicle (e.g. a freezing compartment). Furthermore, vehicles do not need to have the same capacity in the SDVRP.

Multi-depot vehicle routing problem (MDVRP)


Vehicle Count: Multi Vehicle

Depot Count: Multi Depot.

Visiting Restriction: Visit to customer allowed only once, that is, delivery and pick-up should be done at the same visit.

Customer Type Restriction: Can be both linehaul (delivery) customer and backhaul customer (pick-up). A delivery and pick-up can be done at the customer.

Good Restriction: Linehaul (delivery) and a backhaul (pick-up) quantity.

Description:

The MDVRP extends the CVRP by allowing multiple depots. In the MDVRP each customer may be serviced by a vehicle originating at any of the available depots. It requires that each request is assigned to a specific depot. In general, this is a hard optimization problem of its own which needs to be handled together with the routing problem.

Vehicle Routing Problem (VRP) and Traveling Salesman Problem (TSP) Constraints

VRPs can have different constraints in their mathematical model and problem formulation. Some researchers take the constraint as a VRP type discriminating criteria, while others consider them as just additional constraints. Therefore, some VRP types presented in literature are small variants of each other and can be transformed to each other by additional constraints to the problem. That is, they can be considered as the same problem with the additional constraints. In this section, an introductory information on some VRP constraints will be given.

Homogeneous/Heterogeneous Vehicle


Some problems have the constraint that vehicles must be homogeneous. Vehicles may differ in the following properties:

  1. Load types that a vehicle can carry (the vehicle may have more than one compartments for different types of load)
  2. Capacities for each load type (if vehicle has more than one compartment for different load types, each compartments capacity must be considered for each load type)
  3. Fixed cost of a vehicle that is spent at each operation (for example, driver initial fee)
  4. Cost per distance (for example oil cost, driver fee)
  5. Cost per duration (for example driver fee)


Homogeneous/Heterogeneous Load Type


Some problems have the constraint that the load types of orders must be homogeneous. Load types of orders may differ in the following properties:

  1. Types of the load: An order may require that different types of load should be carried, that is heterogeneous load types.
  2. Load/Unload amount for a load type: If there are more than one load type for an order to be carried, then for each load type the load/unload amounts may be heterogeneous.


Maximum Travel Duration


The duration of the travel can be a constraint to the vehicle routing problems. Some examples are:

  1. The problem may have the constraint that a vehicle can not travel more than some specified duration without stopping because of convenience factors or traffic regulations.
  2. The problem may have the constraint that a route can not take longer than some specified duration because of convenience factors or traffic regulations.


Passenger Convenience


Some VRPs deal with passengers. Therefore, passenger convenience is sometimes considered as a constraint on the problem.

Daytime Traffic Condition


Considering a daytime traffic condition is a dynamic constraint which may be included into VRPs. There are many examples on this, some of which are:

  1. In a given time period of day, some roads may be closed for some types of vehicles such as trucks heavier than a specified weight.
  2. In a given date and/or time period, some roads may be closed to some or all types of vehicles because of maintenance, construction, etc.
  3. In some crowded cities, some roads may suffer from heavy traffic in a given period of time.
  4. At some specific date and time, some roads may be closed because of maintenance or traffic accidents.


Visiting Count Restriction


A depot or a station (customer, passenger or node) sometimes require to be visited no more than once, or a specified number of times. This also plays as a constraint on the problems.

Using Vehicle Only In One Route


A vehicle may have been used in several routes or there may be a restriction on the usage of the vehicle more than once in different routes. This sometimes affects the number of used vehicles in the VRP solutions.

Time Windows


If there is a limitation on a delivery and/or pick-up time, then this limitation or restriction is usually referred as time window constraint.

All Deliveries/Pick-ups First


If all the deliveries or pick-ups should be done before any pick-ups or deliveries (respectively), then this may appear as a constraint on the problem.

Vehicle Routing Problem (VRP) Algorithms

In logvrp, Vehicle Routing Problem (VRP) Algorithms are sometimes referred as just VRP Solver or just Algorithm. Current version of logvrp has 2 VRP Algorithms (solvers) built-in.

Jan Dethloff's Algorithm (Modified)


This algorithm is a modified version of Jan Dethloff’s work. It has been modified to support heterogeneous vehicles, load types and time windows.
Solves: VRP with Simultaneous Delivery and Pick-up (VRPSDP)

Reference: Jan Dethloff, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum 23:79–96

Handles constraints: Heterogeneous vehicle, heterogeneous load, visit station once

Adaptive Large Scale Neighborhood Search (ALNS) - Modified


Solves:
  1. VRP with Simultaneous Delivery and Pick-up (VRPSDP)
  2. Vehicle Routing Problem with Time Windows (VRPTW)
  3. Capacitated Vehicle Routing Problem (CVRP)
  4. Site-dependent Vehicle Routing Problem (SDVRP)
  5. Open Vehicle Routing Problem (OVRP)
  6. Multi-Sepot Vehicle Routing Problem (MDVRP)
Reference: David Pisinger and Stefan Røpke. A general heuristic for vehicle routing problems. Technical Report 05/01, DIKU, University of Copenhagen, 2005.

Handles constraints: Heterogeneous vehicle, heterogeneous load, time windows