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.
