Pick up and delivery

Pickup and delivery (PND) problems are one of the most challenging tasks to solve for any Optimizer, yet they are critically important for industries.

Here we would like to present our ideas to solve PND-problems including unique features like production planning additionally to the basic transportation optimization.

Info

This document and the described concepts may change as part of the development process.

Overview

At a glance
Creating NodeDepot, Load, ResourceDepot, and LoadCapacity
Load exchange between a ResourceDepot and a NodeDepot
TimedLoad, FlexLoad, and UnloadAllLoad
Capacity Factor
Analyzing the Result of an Optimization-Run
Closing words

At a glance

Usually, a PND-problem consists of a customer Node that has a request or a supply of goods , and a Resource that tries to serve these demands.

In this example, the Node asks us to:

Deliver three pallets of fruit. (Customer request)
Pick up four bags of waste. (Customer supply)

In our example, a Resource can either fulfil the demand of the customer or provide two possible answers to the requests:

Resource is underloaded: Only one pallet of fruit is available. Check with the Node if partial deliveries are possible.
Resource is overloaded: There is no more transport capacity available on the Resource and the bags of waste cannot be picked up right now.

In short, solving PND-Problems is about an optimal and violation-free exchange of goods between two parties.

In this section, we will describe how JOptTourOptimizer can be used to solve a variety of PND-Problems . Further, we would like to show how JOptTourOptimizer can even be utilized for manufacturing-planning.

Example

Please visit our GitHub-Page for PND-Examples.

Creating NodeDepot, Load, ResourceDepot, and LoadCapacity

NodeDepot, Load, ResourceDepot, and LoadCapacity are the primary objects we will use to define our PND-Problem. Especially Loads are existing in a variety of different flavours to allow defining sophisticated use-cases like:

Time limits between pickup and delivery
Flexible amount of goods allowing for more efficient solutions
Flexible load status being able to change between supply and request

NodeDepot and Load

In JOptTourOptimizer, a Node can keep a NodeDepot. The NodeDepot itself can hold an arbitrary number of Loads (Figure - NodeDepot and Loads).

Screenshot

Figure - NodeDepot and Loads

A NodeDepot can be imagined as a warehouse, which is a helper object to store the actual goods, the Loads. In its simplest version, it only needs a depotId (e.g. "SupermarketDepot") for the initialization.

Loads differ in their loadIds defining the id of the goods we want to exchange and their desired exchange state. A Load in its simplest version is defined via four values, whereas the last three values define the exchange state:

LoadId: The ids of the goods theNode wants to request or supply (e.g. "Bread")
RequestState: Does the Noderequest goods, or supply goods? (for the picking up waste example, set "isRequest = false")
LoadValue: How many items do we supply or request? (e.g. "20")
Fuzzy: Do we allow a partial delivery/pickup? (e.g., "isFuzzy = true")

Implementation Example

In the following paragraph, we create a Node (TimeWindowGeoNode), a NodeDepot (SimpleNodeDepot derived from INodeDepot) and two Loads (SimpleLoad derived from ILoad).

We first create two SimpleLoads, then we create a NodeDepot and add the SimpleLoads to it. In the end, we add the NodeDepot to the Node:

/*
 * Goal: Creating a NodeDepot with two request-loads 
 *        ("Fruit" and "Bread") and attach it to a Node "Supermarket".
 */

// We want "Bread" and "Fruit" to be delivered (we have a request)
boolean isRequest = true;

// We accept partial deliveries of requested goods (fuzzy=true)
boolean isFuzzyAccepted = true;

// We have a fruit request of 20 pallets
ILoad fruitLoad = new SimpleLoad("Fruit", 20, isRequest, isFuzzyAccepted);

// We have a "Bread" request of 5 pallets
ILoad breadLoad = new SimpleLoad("Bread", 5, isRequest, isFuzzyAccepted);

// We create a NodeDepot that can store our different requested loads
INodeDepot supermarketDepot = new SimpleNodeDepot("SupermarketDepot");

// We add the loads to the NodeDepot
supermarketDepot.add(fruitLoad);
supermarketDepot.add(breadLoad);

// We create the Node "Supermarket" and add the NodeDepot
INode supermarket = new TimeWindowGeoNode("Supermarket", 50.9333, 6.95, weeklyOpeningHours, visitDuration, 1);
supermarket.setNodeDepot(supermarketDepot);

Please note that the variables weeklyOpeningHours and visitDuration are not defined in the example above. Please refer to the manual Basic Elements for more information on these variables.

Example

Please see PNDSimpleExample on GitHub for a runnable example of a simple PND-Problem setup.

ResourceDepot and LoadCapacity

In JOptTourOptimizer, as a Node can hold a NodeDepot, a Resource can hold a ResourceDepot. The ResourceDepot itself can keep an arbitrary number of LoadCapacities, e.g. the potential capacity of goods that could be transported. A LoadCapacity is the counterpart to a Load. (Figure - ResourceDepot and LoadCapacities).

Screenshot

Figure - ResourceDepot and LoadCapacities

A ResourceDepot, as part of the truck, is a helper object to store LoadCapacities. In its simplest version a ResourceDepot needs two values:

ResourceDepotdId: The id of the depot. (e.g. "TruckDepot")
Total maximum Capacity: The total value of all goods of all attached LoadCapacities that could potentially be picked up. (e.g. "70")

LoadCapacities mainly differ in their loadCapacityIds (defining the id of the goods it can transport) and their capacity values. A LoadCapacity is defined via three values:

LoadCapacityId: The id of the goods we can transport. (e.g. "Bread")
Individual maximum Capacity: Assuming we only load this one type of goods on the truck, how much can we load before we are overloaded? (e.g. "70") If no further limitations exist, the maximum capacity of an individual LoadCapacity is identical with the maximum capacity of the ResourceDepot it is attached to.
Initial Load value: How many items are already present before starting our trip? (e.g. "5")

Implementation Example

In the following example, we create a Resource (CapacityResource), a ResourceDepot (SimpleResourceDepot derived from IResourceDepot) and two LoadCapacities (SimpleLoadCapacity derived from ILoadCapacity).

We create the two SimpleLoadCapacities before the SimpleResourceDepot and add the SimpleLoadCapacities to it. In the end, we add the SimpleResourceDepot to the Resource:

/*
 * Creating a ResourceDepot with two LoadCapacities and attach it to a Resource
 */

// Define the LoadCapacities "Fruit" and "Bread"

// We can carry a maximum of 40 pallets of fruit (Assuming we have
// no "Bread" on our truck). We start with an initial load of 5 pallets of fruit.
// We can carry a maximum of 40 pallets of fruit. We start with an initial load of 5 pallets of fruit and 10
// initial load pallets of "Bread" of the maximum 30.
ILoadCapacity fruitLoadCapacity= new SimpleLoadCapacity("Fruit", 70, 5);

ILoadCapacity breadLoadCapacity = new SimpleLoadCapacity("Bread", 70, 10);

// We create a ResourceDepot that can store our different LoadCapacities
// The depot can handle a total of 70 pallets 
IResourceDepot depot = new SimpleResourceDepot("truckDepot", 70);

// We add the capacityLoads to the depot
depot.add(fruitLoadCapacity);
depot.add(breadLoadCapacity);

// We create a Resource "Truck" and  add the depot to our Resource
IResource truck = new CapacityResource("Truck", 50.1167, 7.68333, maxWorkingTime, maxDistanceKmW, workingHours);
truck.setResourceDepot(depot);

Example

See PNDSimpleExample on GitHub.

Load-exchange between a ResourceDepot and a NodeDepot

To better understand the outlined concepts, we will have a closer look into how the Optimizer performs the load-exchange between a ResourceDepot and a NodeDepot. Subsequently, we will focus on violations that can occur during a load-exchange.

Load-Exchange

The Loads of a NodeDepot and the LoadCapacities of a ResourceDepot are the counterparts during a load-exchange.

A NodeDepot contains the requests/supplies of goods (Loads) desired by a customer. The ResourceDepot holds the information on the potential and the actual amount of goods (LoadCapacity) on the transport vehicle that are requested/supplied. Each Load of a NodeDepot needs a corresponding LoadCapacity of a ResourceDepot for a successful exchange. Further, the loadCapacityId and the corresponding loadId have to match (for example, a Load with loadId "Fruit" and a LoadCapacity with the identical loadCapacityId "Fruit").

Screenshot

Figure - Load Exchange.

"Figure - Load Exchange" shows a successful and violation-free exchange of two goods, "Fruit" and "Bread". The fruitLoadCapacity before the visit has a load value of 30 and supplies the NodeDepot with the desired 20 items of "Fruit". Therefore, after the visit, 10 "Fruit" are left on the truck and the fruitLoadCapacity has a new load value of 10.

In a PND-Problem a Resource usually visits multiple customer Nodes in the same Route. During the Optimization, several different solutions including different visit-orders are evaluated.

Screenshot

Figure - Multi visit.

"Figure - Multi visit" shows a typical solution of a single Route of a PND-Problem. A Resource starts with an initial load value of 28 "Bread" of a maximum capacity of 30.

The first customer Node requests 22 "Bread". After the visit the truck still has 6 "Bread" left.
The subsequent Node B supplies the Resource with 3 "Bread" to a new capacity value of 9.
The last customer Node C requests 12 "Bread". As we only have 9 "Bread" left we are underloaded and can't fulfil the customer's request completely. However, since the customer in this example also accepts a fuzzy delivery, we can at least supply him with the 9 "Bread" that are available.

Types of Capacity Violations

JOpt-TourOptimizer distinguishes between several violation types. "Figure - Multi visit" already shows an example of an underload violation. An underload violation can occur in two different ways.

"Figure - Underload Violations" summarizes the underload violations that can occur.

Screenshot

Figure - Underload Violations.

Underload: The ResourceDepot has not enough goods left in the LoadCapacity to serve the customer request.
Underload-NO-MATCH: The Resource does not have a ResourceDepot attached which contains the LoadCapacity with a corresponding loadCapacityId to the loadId the customer Node requested.

Another type of violation is an overload-violation. In case a Node wants to supply too many goods, a ResourceDepot may reject the admission. An overload-violation can occur either because of total overloading or because of individual overloading. "Figure - Overload Violations" summarizes the overload violations that can occur.

Screenshot

Figure - Overload Violations.

Individual overloading: Each LoadCapacity within a ResourceDepot has a maximum individual capacity. This value describes the maximum amount of that type of goods that could be loaded on the truck. The individual maximal capacity of a specific LoadCapacity are equal to the total maximal capacity of the ResourceDepot, assuming all space could be used by any LoadCapacity. However, JOpt-Touroptimizer solves more customized problems as well: In this example, a truck has a cold storage room for a special LoadCapacity type "FrozenMeat" installed. Since the freezer takes up half the truck's floor-space, this LoadCapacity’s individual maximum capacity is only half the size of the total maximum capacity of the ResourceDepot. In case the freezer is full, it is not possible to store more units of "FrozenMeat" even though the other half of the (non-cooled) floor space is still empty.
Total overloading: A ResourceDepot has a maximum total capacity. This capacity includes all goods a ResourceDepot is allowed to store. Let's look at the ResourceDepot from "Figure - Overload Violations", that is requested to pick up 30 "Fruit" and 25 "Bread" from a single NodeDepot. The total capacity of the ResourceDepot is 50. Further, the initial load value of "Fruit" is zero, and the initial load value of "Bread" is 15. "Fruit" is the first Load that gets transferred. As the initial load value of the LoadCapacity is zero, 30 pallets of "Fruit" get transferred. After the first exchange, the LoadCapacity has a loadValue of 30 "Fruit" + 15 "Bread" = 45 items. As the total capacity is 50, the ResourceDepot can only accept 5 additional "Bread" (instead of 25) to avoid total overloading.

Info

A ResourceDepot can never supply more goods than its LoadCapacities contain => The requesting NodeDepot gets fewer goods delivered than requested if the request exceeds the goods in the ResourceDepot. Further, a ResourceDepot never takes more goods than it's the maximum capacity, defined through its total and individual LoadCapacity limitations => The supplying NodeDepot keeps the Loads the ResourceDepot rejects.

TimedLoad, FlexLoad, and UnloadAllLoad

Up to now, we only looked at SimpleLoads. Timed, flexible, and unloadAll loads are special kinds of Loads. A TimedLoad predefines a duration, during which goods need to be picked up and delivered. In case the maximum duration is violated, the solution gets a penalty cost assigned through a soft-constraint. A FlexibleLoad can generate an additional supply or a request, depending on the needs for the solution of the PND-Problem. An UnloadAllLoad can request all goods of a ResourceDepot.

In the following paragraph, we provide an overview of the different Load types, before outlining some example use-cases.

Overview of Load Types

In "Figure - Types of Load", the different types of Loads and their relations are outlined. It is possible to distinguish between four main types of Loads:

Simple Load: User-defined load value and user-defined load status (request or supply).
Timed Load: Mandatory load value of one that can't be changed and user-defined load status (request or supply). Further, a user-defined duration describing how long a Load is allowed to stay in a ResourceDepot after the TimedLoad got picked up. In a real-world example this would be the time the goods spend "on the road" in the truck. In case the maximum duration is violated, an OVERTIME violation is reported and the solution receives a penalty cost.
MixedFlex Load: The load value (initially zero or a user-defined) is allowed to change as a result of the Optimization. The load status (request or supply) is also allowed to change as a result of the Optimization.
UnloadAll Load: Load value will adjust itself to request one or several LoadCapacities of a ResourceDepot completely.

Screenshot

Figure - Types of Load.

Beside the main types of Loads, several further sub-types can be used. In the following paragraph, we distinguish between three sub-types:

RequestFlex Load: Like a MixedFlexLoad where the Optimizer sets the load value and the load status is set to request.
SupplyFlex Load: Like a MixedFlexLoad where the Optimizer sets the load value and the load status is set to supply.
TimedSupplyFlex Load: A hybrid between TimedLoad and SupplyFlexLoad. Mandatory load value of zero or one and mandatory load status of supply. The load value is allowed to be changed by the Optimizer to be either zero or one. A user-defined duration describes how long a LoadCapacity is allowed to stay in a ResourceDepot after the Load got picked up from a NodeDepot.

Use-Cases for Load Types

The following examples should provide some further insight into how each of the described Load types can be utilized. Please also visit our GitHub-Page for PND-Examples.

Example TimedLoad

A cab-company has to transport three people (Max, Peter, and Lars). For this purpose, the cab-driver has to pick up each of them at a particular place and drop them at another location. The cab-driver is allowed to have a maximum of three different passengers at the same time. Max, Peter and Lars have different pickup and destination places. The cab-company promised each of them that each trip would take no more than one hour.

Task for the Optimizer: Pickup and deliver each of the passengers to their destination within one hour.

Example

Example on GitHub: PNDTimedLoadExample.

Example MixedFlexLoad

A Resource has to deliver/pickup "Fridges" and deliver/pickup "TVs". Each customer Node can decide what needs to be picked up or delivered by the Resource. As planning the initial load for a truck can be challenging in mixed pickup and delivery problems, we use a MixedFlexLoad that can adjust its request or supply status during Optimization. Here a MixedFlexLoad can be seen as a warehouse that a Resource can use to reload and/or unload goods to avoid over-and underloading. A MixedFlexLoad, like all other Loads, is member of an INodeDepot. For a better overview, we attach the MixedFlexload to a separate NodeDepot and add it to the Node "WarehouseNode" only added to keep this NodeDepot and the contained MixedFlexLoad.

Task for the Optimizer: Find the optimal load value and load status for "Fridges" and "TVs" to avoid over- and/or underloading of the ResourceDepot. The MixedFlexLoad of the separately added "WarehouseNode" serves as a buffer.

Info

When using the concept of MixedFlexLoad (or the related Supply- and RequestFlexLoad), we suggest creating a dedicated Node for the sole purpose of acting as warehouse node. While it is possible to attach FlexLoads to any NodeDepot of any Node, we recommend creating dedicated Nodes with NodeDepots carrying FlexLoads for the sake of comprehensibility and overview.

Example

Example on GitHub: PNDMixedFlexLoadExample.

Example RequestFlexLoad

Building on the example of the MixedFlexLoad, we assume instead of having a full-fledged warehouse, we only have temporary storage capability, for example at the Resources home. The Resource gets 6 "Fridges" in the morning, but realizes it only needs 2 for the Route. It will leave 4 at the MixedFlexLoad and therefore has more room for other supply or pick up tasks.

Task for the Optimizer: Find the optimal Load value for "Fridges" and "TVs" to avoid overloading of the ResourceDepot.

Example

Example on GitHub: PNDRequestAndSupplyFlexLoadExample.

Example SupplyFlexLoad

In this example, two Resources called "JackTruckCologne" and "JohnTruckAachen" are employees of a bakery chain and have to deliver "Bread" to different supermarkets. Each supermarket can define its request. Each of the Resources is bound to a different bakery at a different location. Two SupplyFlexLoads are added to the NodeDepots where each of them can get supplied on an optimizer-defined value of pallets of bread. The optimized amount of goods of each SupplyFlexLoad describes the optimal number of pallets of bread each bakery has to prepare. In this case, the Optimizer has done the production planning.

For an overview of manufacturing-planning problems please click here.

Task for the Optimizer: Find the optimal load value for each SupplyFlexLoad to avoid underloading and serve all supermarkets with "Bread".

Example

Example on GitHub: PNDBackeryChainFlexLoadExample.

Example TimedSupplyFlexLoad

In this example, we have two pizza restaurants of the same company-chain. One is situated in Cologne and the other one in Essen. Each restaurant has one delivery man. For every customer order, the restaurants can decide which local branch is serving the request.

The restaurant chain advertises: "If you don't get your pizza within 90 minutes, you get if for free!". Therefore, each pizza should be delivered within 90 minutes. Two TimedSupplyFlexLoads describe two orders that can contain several user-defined types of pizza (e.g., "Pizza Margherita" for customer Tom, or "Pizza Mexican" for customer Sophia). Manufacturing-planning is solved by the Optimizer. The optimized load value (zero or one) of each TimedSupplyFlexLoad describes the pizzas each restaurant has to prepare in order to make sure they arrive within 90 minutes.

Task for the Optimizer: Deliver each pizza within 90 minutes. The final optimized load values of each SupplyFlexLoad will be used to decide which restaurant will prepare which pizza automatically.

Example

Example on GitHub: PNDTimedPizzaDeliveryExample.

Example UnloadAllLoad

A Resource has to pick up "Waste" from customers (customer supply). After visiting a few customers, the ResourceDepot is full. To avoid overload, multiple UnloadAllLoads can be visited to unload "Waste" (request) completely. Here, each UnloadAllLoad acts as a landfill. Each UnloadAllLoad is bound to a separate NodeDepot of a separate optional node.

Info

An UnloadAllLoad can also be implemented by using a Mixed- or RequestFlexLoad. However, in the case where it is evident that the Resource will unload everything, it is recommended to use an UnloadAllLoad, as this saves the Optimizer from doing unnecessary computational work.

Task for the Optimizer: Position the waste dumps along the Route. Identify which waste dumps need to be visited to avoid overloading of the Resource.

Example

Example on GitHub: PNDOptionalUnloadAllLoadExample.

Capacity Factor

Up to now, we silently assumed that every single Load has the same space-dimensions/weight as any another Load. In reality, however, some Loads require more space than others. Further, some Loads can be stacked, and other Loads cannot.

Let's assume the following example: A Resource called JackTruck has to deliver/pickup "Pianos" and has to deliver/pickup "Cups". Each customer can decide what needs to be picked up (customer supply) and what needs to be delivered (customer request).

Evidently a Resource truck can load more units of "Cups" than units of "Pianos". Let's assume the "Cups" are transported on pallets the size of 1219 x 1016 mm. We do not allow to stack the pallets as otherwise, "Cups" could break. Each customer Node is only allowed to request or provide pallets of cups, not single cups. A piano has a floor space of 160 x 140 cm. Obviously, we cannot stack pianos either (Figure - Dimensions of Loads).

Screenshot

Figure - Dimensions of Loads.

The truck has a floor space of 7 x 2.5 m. The goal is to find a way to tell the Optimizer the maximum amount of both goods that a Resource truck can carry without overloading. For this, we have to calculate the equivalent of one piano and one pallet of cups. The ground unit for this calculation is square-meter. What is the equivalent of a "Piano" and what is the equivalent of a pallet of "Cups" in this ground unit?

Example

JOptTourOptimizer already includes the class CargoSpace to do the required calculations (Example on GitHub).

Maximal individual Load

The maximal individual load describes the maximal amount of goods of a particular type if no other goods are present. The following code shows an example of how the maximal individual load can be calculated:

// Define the cargo space of the truck
ICargoSpace truckCargoSpace =
  new CargoSpace(
    Quantities.getQuantity(7.0, METRE), Quantities.getQuantity(2.5, METRE));

// Define the cargo goods for the piano
ICargoSpaceGood pianoCargoGood =
  new CargoSpaceGood(
    Quantities.getQuantity(160, CENTI(METRE)), Quantities.getQuantity(140, CENTI(METRE)));

// Define the cargo good for the cups
ICargoSpaceGood cupsCargoGood =
   new CargoSpaceGood(
    Quantities.getQuantity(1219, MILLI(METRE)), Quantities.getQuantity(1016, MILLI(METRE)));

// What would be the maximal individual  Load of a certain good in our truckCargoSpace?
double maxPianoLoad = pianoCargoGood.calculateMaxIndividualLoading(truckCargoSpace);
double maxCupLoad = cupsCargoGood.calculateMaxIndividualLoading(truckCargoSpace);

// Result: maxPianoLoad = 4 and maxCupLoad = 10

// Now we can define the individual load Capacities for Piano and Cup
// Note: The initial load is NOT an abstract unit. Here it is the number of Pianos and number of
// pallets that are already on the truck.
ILoadCapacity pianoCapacity = new SimpleLoadCapacity("Piano", maxPianoLoad, 2);
ILoadCapacity cupCapacity = new SimpleLoadCapacity("Cup", maxCupLoad, 5);

Executing the above example leads to a maximal individual pianoLoad of 4 and a cupLoad of 10, which means we can either load 4 Pianos or 10 pallets of cups. What if we have to load 2 "Pianos" and 6 pallets of "Cups"? Are we already overloaded? In order to find out, we have to relate "Pianos" and pallets of "Cups" to a ground unit defined by the ResourceDepot truck. This relation is established by calculating the CapacityFactors for "Piano" and pallets of "Cups".

Calculating the Capacity Factors

In the following example, we calculate these CapacityFactors based on the ResourceDepot ground unit and try to give the unit of the CapacityFactors for this problem:

// Calculate the max loading in the ground unit - For space, this is in square meter
double maxTotalLoadValue = truckCargoSpace.calculateMaxTotalLoadingCapacity();

// Result: maxTotalLoadValue = 17.5

// Define a depot for our truck that has a capacity (defined in the ground unit)
IResourceDepot depot = 
   new SimpleResourceDepot("JackTruckDepot", maxTotalLoadValue);

// Calculate the individual loading factors:
// =========================================
// The loadFactor calculation can fail, in case the maximal individual load
// would be zero. Therefore an Optional is returned.

Optional<Double> pianoLoadFactorOpt = 
   truckCargoSpace.calculateLoadingCapacityFactor(pianoCargoGood);

Optional<Double> cupsLoadFactorOpt = 
       truckCargoSpace.calculateLoadingCapacityFactor(cupsCargoGood);

// Result: pianoLoadFactor = 4.375 and maxCupLoad = 1.75

// Add the factors, if existing
if (pianoLoadFactorOpt.isPresent()) {
    Double pianoLoadFactor = pianoLoadFactorOpt.get();
    depot.add("Piano", pianoLoadFactor);
}

if (cupsLoadFactorOpt.isPresent()) {
    Double cupsLoadFactor = cupsLoadFactorOpt.get();
    depot.add("Cup", cupsLoadFactor);

}

// Add the loadCapacities
depot.add(pianoCpacity);
depot.add(cupCpacity);

The maximum total load capacity of the truck is 17.5. This value is the floor space size in the unit of square-meters. For the CapacityFactors, we found 1.75 (pallet of cups) and 4.375 (Piano). These values are also the individual floor spaces each of the goods takes up.

After performing the described initialization, we can run the Optimization.

Example

Example on GitHub: PNDCapacityFactorExample.

Analyzing the Result of an Optimization-Run

After solving a PND-Problem, the Optimizer gives the default result output. Now we want to understand the way the Optimizer reports a PND-Result.

Info

The outlined description describes the default output by the Optimizer. However, usually the report needs to be parsed to a user-defined format. Please follow PNDReportExtractionExample on our GitHub-Page for help.

When running Example PNDBackeryChainFlexLoadExample, we get the following result:

Press to expand or close result example

-------------------------------- --------------------------
--------------------- RESULTS -----------------------------
----------------- -----------------------------------------
 Number of Route         : 2
 Number of Route (sched.): 2
 Total Route Elements    : 10
 Total cost              : 627.4498933084467
-----------------------------------------------------------
 Total time        [h]   : 17
 Total idle time   [h]   : 0
 Total prod. time  [h]   : 10
 Total tran. time  [h]   : 6
 Total utilization [%]   : 61
 Total distance    [km]  : 540
 Termi. time       [h]   : 3
 Termi. distance   [km]  : 256

----------------------- -----------------------------------
--------------------- ROUTES ------------------------------
---------------------- ------------------------------------

-----------------------------------------------------------
Route information
Route Status           : Optimizable
RouteId                : 0
Resource               : JackTruckCologne
Alternate destination  : false
Closed route           : true
Defined WorkingHours   : 11.03.2020 08:00:00 - 11.03.2020 20:00:00 (Europe/Berlin)
Effective Route Start  : 11.03.2020 08:00:00 (Europe/Berlin)
Effective Route Stop   : 11.03.2020 17:40:52 (Europe/Berlin)
Max Idle Reduc.  [min] : 0.0
Max Early Redu.  [min] : 0.0
Max Early P-Redc.[min] : 0.0
Reduc. time usage[min] : 0
Max Post Reduc.  [min] : 0.0
Post time usage  [min] : 0
WorkingHours Index     : 0
-----------------------------------------------------------
Route cost             : 392.7634772786474
Route time       [min] : 580
Transit time     [min] : 260
Productive. time [min] : 320
Idle time        [min] : 0
White Idle time  [min] : 0
Ind. Idle time   [min] : 0
Route Distance   [km]  : 344.357
Termi. time      [min] : 122
Termi. distance  [km]  : 162.097
Utilization      [%]   : 53
Start Id               : JackTruckCologne
Termination Id         : JackTruckCologne

------- ResourceDepot Report (JackTruckCologne)-------
START:
---
Id: JackTruckCologneDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0
(0) LoadCapacity:
Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /

TERMINATION:
---
Id: JackTruckCologneDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0
(0) LoadCapacity:
Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /
------- ResourceDepot Report END -------

0.0 SupplyFlexNodeCologne / Arrival: 11.03.2020 08:00:00 (Europe/Berlin) , Departure: 11.03.2020 09:20:00 (Europe/Berlin) / Duration: 80 [min] / Driving: 0.0 [min], 0.0 [km]
Depot before visit: Id: SupplyFlexNodeCologneDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SupplyFlexLoad / Desired Load Exchange: 14.0 / IsRequest: false / IsFuzzy: false / Priority: 1]
Depot after visit : Id: SupplyFlexNodeCologneDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SupplyFlexLoad / Desired Load Exchange: 0.0 / IsRequest: false / IsFuzzy: false / Priority: 1]

0.1 StoreEssen / Arrival: 11.03.2020 10:03:38 (Europe/Berlin) , Departure: 11.03.2020 11:23:38 (Europe/Berlin) / Duration: 80 [min] / Driving: 43.64 [min], 57.605 [km]
Depot before visit: Id: StoreEssenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 5.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreEssenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

0.2 StoreDortmund / Arrival: 11.03.2020 11:48:49 (Europe/Berlin) , Departure: 11.03.2020 13:08:49 (Europe/Berlin) / Duration: 80 [min] / Driving: 25.19 [min], 33.245 [km]
Depot before visit: Id: StoreDortmundDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 8.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreDortmundDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

0.3 StoreBielefeld / Arrival: 11.03.2020 14:18:04 (Europe/Berlin) , Departure: 11.03.2020 15:38:04 (Europe/Berlin) / Duration: 80 [min] / Driving: 69.25 [min], 91.408 [km]
Depot before visit: Id: StoreBielefeldDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 1.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreBielefeldDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]


ViolationSumary:
Cost TotalSum: 48.40637916666667,Cost RouteTime: 48.40637916666667
-----------------------------------------------------------
Route information
Route Status           : Optimizable
RouteId                : 1
Resource               : JohnTruckAachen
Alternate destination  : false
Closed route           : true
Defined WorkingHours   : 11.03.2020 08:00:00 - 11.03.2020 20:00:00 (Europe/Berlin)
Effective Route Start  : 11.03.2020 08:00:00 (Europe/Berlin)
Effective Route Stop   : 11.03.2020 15:48:13 (Europe/Berlin)
Max Idle Reduc.  [min] : 0.0
Max Early Redu.  [min] : 0.0
Max Early P-Redc.[min] : 0.0
Reduc. time usage[min] : 0
Max Post Reduc.  [min] : 0.0
Post time usage  [min] : 0
WorkingHours Index     : 0
-----------------------------------------------------------
Route cost             : 234.68641602979932
Route time       [min] : 468
Transit time     [min] : 148
Productive. time [min] : 320
Idle time        [min] : 0
White Idle time  [min] : 0
Ind. Idle time   [min] : 0
Route Distance   [km]  : 195.667
Termi. time      [min] : 71
Termi. distance  [km]  : 93.938
Utilization      [%]   : 53
Start Id               : JohnTruckAachen
Termination Id         : JohnTruckAachen

------- ResourceDepot Report (JohnTruckAachen)-------
START:
---
Id: JohnTruckAachenDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0
(0) LoadCapacity:
Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /

TERMINATION:
---
Id: JohnTruckAachenDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0
(0) LoadCapacity:
Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /
------- ResourceDepot Report END -------

1.0 SupplyFlexNodeAachen / Arrival: 11.03.2020 08:00:07 (Europe/Berlin) , Departure: 11.03.2020 09:20:07 (Europe/Berlin) / Duration: 80 [min] / Driving: 0.12 [min], 0.156 [km]
Depot before visit: Id: SupplyFlexNodeAachenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SupplyFlexLoad / Desired Load Exchange: 13.0 / IsRequest: false / IsFuzzy: false / Priority: 1]
Depot after visit : Id: SupplyFlexNodeAachenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SupplyFlexLoad / Desired Load Exchange: 0.0 / IsRequest: false / IsFuzzy: false / Priority: 1]

1.1 StoreDueren / Arrival: 11.03.2020 09:41:35 (Europe/Berlin) , Departure: 11.03.2020 11:01:35 (Europe/Berlin) / Duration: 80 [min] / Driving: 21.47 [min], 28.344 [km]
Depot before visit: Id: StoreDuerenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 2.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreDuerenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

1.2 StoreLeverkusen / Arrival: 11.03.2020 11:35:45 (Europe/Berlin) , Departure: 11.03.2020 12:55:45 (Europe/Berlin) / Duration: 80 [min] / Driving: 34.17 [min], 45.102 [km]
Depot before visit: Id: StoreLeverkusenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 7.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreLeverkusenDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

1.3 StoreWuppertal / Arrival: 11.03.2020 13:17:04 (Europe/Berlin) , Departure: 11.03.2020 14:37:04 (Europe/Berlin) / Duration: 80 [min] / Driving: 21.31 [min], 28.125 [km]
Depot before visit: Id: StoreWuppertalDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 4.0 / IsRequest: true / IsFuzzy: true / Priority: 1]
Depot after visit : Id: StoreWuppertalDepot / Type: SimpleNodeDepot / Loads: [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]


ViolationSumary:
Cost TotalSum: 39.01938055555556,Cost RouteTime: 39.01938055555556

Let's have a look at the PND-related parts of the result. They can be distinguished into two parts:

ResourceDepot-Report: The initial Load we start with and the final Load after the Resource is done with the Route. (One report per Route)
NodeDepot-Report: The desired exchange before being visited and the desired exchange after being visited. (One report per Node per Route)

ResourceDepot-Report

The ResourceDepot-Report of a Resource is divided into two parts:

START: The properties of the ResourceDepot BEFORE we start the Route.
TERMINATION: The properties of the ResourceDepot AFTER we finished the Route.

------- ResourceDepot Report (ID_OF_THE_RESOURCE)-------
START:
---
...

TERMINATION:
---
...
------- ResourceDepot Report END -------

"Figure - ResourceDepot Start and Termination" shows a graphical representation of the two ResourceDepots (at start and at termination).

Screenshot

Figure - ResourceDepot Start and Termination

Inside the start and termination parts, we find information about the ResourceDepot and its LoadCapacities. The presented results are formatted for easier readability:

   Id:               JackTruckCologneDepot / 
   Type:             SimpleResourceDepot  / 
   MaxTotalCapacity: 20.0 / 
   UsedCapacity:     0.0

   (0) LoadCapacity: 
       Id:            Bread / 
       Type:          SimpleLoadCapacity / 
       Load:          0.0 / 
       maxCapacity:   20.0 /

With the following definitions:

Properties of the ResourceDepot:
- Id: The id of the ResourceDepot. (e.g. "JackTruckCologneDepot")
- Type: The type of the ResourceDepot. (e.g. "SimpleResourceDepot")
- MaxTotalCapacity: The maximum total capacity. (e.g. "20")
- UsedCapacity: The currently used total capacity, including all Loads. (e.g., "0" if there is no loading)
Properties of LoadCapacities:
- (n) LoadCapacity: The nth index of the LoadCapacity inside the ResourceDepot. (e.g. "(0)")
- Id: The id of the LoadCapacity. (e.g. "Bread")
- Type: The type of the LoadCapacity (e.g. "SimpleLoadCapacity")
- Load: The current loadValue of the LoadCapacity. (e.g. "0")
- maxCapacity: The maximal individual capacity of the LoadCapacity. (e.g. "20")

The full report (unformatted) looks like this:

------- ResourceDepot Report (JohnTruckAachen)-------
START:
---
Id: JohnTruckAachenDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0

(0) LoadCapacity: 
 Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /

TERMINATION:
---
Id: JohnTruckAachenDepot / Type: SimpleResourceDepot  / MaxTotalCapacity: 20.0 / UsedCapacity: 0.0

(0) LoadCapacity: 
 Id: Bread / Type: SimpleLoadCapacity / Load: 0.0 / maxCapacity: 20.0 /
------- ResourceDepot Report END -------

The report can be described as follows:

A Resource with the id "JohnTruckAachen" and an attached ResourceDepot with the id "JohnTruckAachenDepot" is allowed to carry a LoadCapacity with the id "Bread". The maximal total capacity of the ResourceDepot is 20. Further, the maximal individual capacity is also 20.

Before starting, the Resource truck is empty, as the load value of Bread is zero. After the Route is finished, the load value is also zero, meaning that there is no "Bread" left on the truck.

NodeDepot-Report

Now, let's analyze the NodeDepot-Report. For this purpose we have a look at the output for a single node:

1.2 StoreLeverkusen / Arrival: 11.03.2020 11:35:45 (Europe/Berlin) , Departure: 11.03.2020 12:55:45 (Europe/Berlin) / Duration: 80 [min] / Driving: 34.17 [min], 45.102 [km]

 Depot before visit: Id: StoreLeverkusenDepot / Type: SimpleNodeDepot / Loads: 
 [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 7.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

 Depot after visit : Id: StoreLeverkusenDepot / Type: SimpleNodeDepot / Loads: 
 [ Id: Bread / Type: SimpleLoad / Desired Load Exchange: 0.0 / IsRequest: true / IsFuzzy: true / Priority: 1]

The first lines of the output describe the characteristic properties of a Node result (node-Id, the arrival, the departure, the duration, and other properties (See: First optimization).

The second part describes the NodeDepot BEFORE and AFTER the visit. Or in other words, it represents the load-exchange between a visiting ResourceDepot and the NodeDepot.

"Figure - NodeDepot Before and After" shows a graphical representation of two NodeDepots of a particular Node before and after being visited by a Resources' ResourceDepot.

Screenshot

Figure - NodeDepot Before and After

For a better understanding, we first analyze the NodeDepot before exchange:

The Report for the NodeDepot before visits contains information about the NodeDepot and each of its Loads. The shown result are formatted here for easier readability:

  Depot before visit: 

   Id:   StoreLeverkusenDepot / 
   Type: SimpleNodeDepot / 

   Loads: 
      [ 
      Id:           Bread / 
      Type:         SimpleLoad / 
      Desired Load 
      Exchange:     7.0 / 
      IsRequest:    true / 
      IsFuzzy:      true / 
      Priority:     1
      ]

With the following definitions:

Properties of the NodeDepot:
- Id: The id of the NodeDepot. (e.g. "StoreLeverkusenDepot")
- Type: The type of the NodeDepot. (e.g. SimpleNodeDepot)
- Loads: A list of Loads, the NodeDepot is able to exchange. The Loads are represented within brackets " [Load1, Load2,...]".
Properties of each Load:
- Id: The id of the Load. (e.g. "Bread")
- Type: The type of the Load. (e.g. SimpleLoad)
- Desired Load Exchange: How much loadValue should be exchanged? For example, a value of 7 "Bread" needs to be delivered.
- IsRequest: Does the NodeDepot request goods (true), or does the NodeDepot supply goods (false)?
- IsFuzzy: Are partial deliveries and pick ups allowed?
- Priority: In case multiple Loads are exchanged, Loads with higher priority are exchanged first.

The report AFTER the visit looks more or less the same. The significant difference is the desired exchange-value:

  Depot after visit: 

   Id:   StoreLeverkusenDepot / 
   Type: SimpleNodeDepot / 

   Loads: 
      [ 
      Id:           Bread / 
      Type:         SimpleLoad / 
      Desired Load 
      Exchange:     0.0 / 
      IsRequest:    true / 
      IsFuzzy:      true / 
      Priority:     1
      ]

Before the visit, we had a request of 7 "Bread" and after the exchange visit we have a request of 0. Therefore, we were able to satisfy the request of 7 units of "Bread". In case the ResourceDepot would not have been able to deliver 7 units but only 5, the NodeDepot would be left with a remaining request of 2.

Closing Words

This document and the outlined concepts may change as part of the development process.

Pick up and delivery

Overview

At a glance

Creating NodeDepot, Load, ResourceDepot, and LoadCapacity

NodeDepot and Load

Implementation Example

ResourceDepot and LoadCapacity

Implementation Example

Load-exchange between a ResourceDepot and a NodeDepot

Load-Exchange

Types of Capacity Violations

TimedLoad, FlexLoad, and UnloadAllLoad

Overview of Load Types

Use-Cases for Load Types

Example TimedLoad

Example MixedFlexLoad

Example RequestFlexLoad

Example SupplyFlexLoad

Example TimedSupplyFlexLoad

Example UnloadAllLoad

Capacity Factor

Maximal individual Load

Calculating the Capacity Factors

Analyzing the Result of an Optimization-Run

ResourceDepot-Report

NodeDepot-Report

Closing Words

Authors