Pick up and delivery

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

Here we would like to present our idea to solve PND-Problems. Further, we explore unique features, for example, a way to use our PND-system for the manufacturing-planning of goods besides basic transportation Optimization.

Info

The outlined concept is in beta-status. Therefore, this document and the described concepts may change as part of the development process.


Overview


On a glance

When thinking of PND-Problems, usually, there is a customer (Node) that has a request (or a supply) of goods, and a Resource that tries to serve these demands.

The customer, for example, defines:

  • Please deliver three pallets of fruits. (Customer request)
  • Please pick up four bags of rubbish. (Customer supply)

A Resource can either fulfill the demand of the customer or can raise, for example, the following problems:

  • Sorry, I have only one pallet of fruits available. Do you agree to take only one pallet at the moment? (Resource is underloaded)
  • Sorry, I'm already full of goods. I can't accept any further bags of rubbish. (Resource is overloaded)

In short, solving PND-Problems is about a desirably optimal violation-free exchange of goods (loads) between two parties (here, a NodeDepot and a ResourceDepot).

Here, we would like to describe how JOptTourOptimizer can be used to solve a variety of PND-Problems. Further, we would like to show how JOptTourOptimizer can be even 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 flavors to allow defining sophisticated use-cases like:

  • How long are goods allowed to stay on a truck between pickup and delivery?
  • What amount of goods do I need to serve all customers?
  • ... etc.

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, usually, is a simple helper object to store Loads. In its simplest version, it only needs a DepotId (e.g. "SupermarketDepot") for 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 (the last three values define the exchange state):

  1. LoadId: The id of the goods we want to request or supply (e.g. "Bread")
  2. RequestState: Do we request goods, or do we supply goods? (e.g. "isRequest = true")
  3. LoadValue: How many items do we supply or request? (e.g. "20")
  4. Fuzzy: Do we allow a partial delivery/pickup? (e.g., "isFuzzy = true")

Implementation Example

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

We first create two simple loads than we create a simple NodeDepot and add the loads 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 breads and fruits to be delivered (we have a request)
boolean isRequest = true;

// In case a truck can only deliver a partial amount of our requested
// goods, we accept that (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 depot
supermarketDepot.add(fruitLoad);
supermarketDepot.add(breadLoad);

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

// ... and add the depot to our Node
supermarket.setNodeDepot(supermarketDepot);

Please note, in the example shown above, the variable weeklyOpeningHours and visitDuration is not defined. Please refer to the manual Basic Elements.

Example

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


ResourceDepot and LoadCapacity

In JOptTourOptimizer, a Resource can hold a ResourceDepot. The ResourceDepot itself can keep an arbitrary number of LoadCapacities (Figure - ResourceDepot and LoadCapacities).

Screenshot

Figure - ResourceDepot and LoadCapacities

A LoadCapacity is the counterpart to Loads. A ResoruceDepot is a helper object to store LoadCapacities. In its simplest version it needs two values:

  1. ResourceDepotdId: The id of the depot. (e.g. "TruckDepot")
  2. Total maximal capacity: The total load value (of all goods) that can be stored before the ResourceDepot gets overloaded. (e.g. "70")

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

  1. LoadCapacityId: The id of the goods we can transport. (e.g. "Bread")
  2. Individual maximal capacity: Assuming we load only a particular type of goods on a truck, how much can we load before we are overloaded? (e.g. "40")
  3. Initial load value: How many items are already present, before starting our trip? (e.g. "5")

Implementation Example

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

We first create two simple LoadCapacities, than we create a simple ResourceDepot and add the LoadCapacities to it. In the end, we add the ResourceDepot to the Resource:

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

// Define the LoadCapacities fruit and bread

// We are able to carry a maximum of 40 pallets of fruit (Assuming we have
// no breads on our truck). We start with an initial load of 5 pallets of fruit.
ILoadCapacity fruitCapacityLoad = new SimpleLoadCapacity("fruit", 40, 5);

// We are able to carry a maximum of 30 pallets of bread (Assuming we have
// no fruit on our truck). We start with an initial load of 10 pallets of bread.
ILoadCapacity breadCapacityLoad = new SimpleLoadCapacity("bread", 30, 10);

// We create a ResourceDepot that can store our different capacityLoads
// The depot can handle a maximum of 70 pallets (for example, 
// 40 pallets of fruit and 30 pallets of bread)
IResourceDepot depot = new SimpleResourceDepot("truckDepot", 70);

// We add the capacityLoads to the depot
depot.add(fruitCapacityLoad);
depot.add(breadCapacityLoad);

// We create a Resource "Truck"...
IResource truck = new CapacityResource(
    "Truck", 50.1167, 7.68333, maxWorkingTime, maxDistanceKmW, workingHours);

// ... and add the depot to our Resource
truck.setResourceDepot(depot);

Load-exchange between a ResourceDepot and a NodeDepot

For a better understanding of the outlined concepts, we will have a look into the way 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 collects the requests/supplies of goods desired by a customer. The ResourceDepot collects the capacity for the requested/supplied goods. Each Load of a NodeDepot needs a corresponding LoadCapacity of a ResourceDepot for a successful exchange. Further, to identify which Loads corresponds to which LoadCapacity the loadId and the capacityLoadId have to match (for example, a Load with loadId "Fruit" and a LoadCapacity with the identical capacityLoadId "Fruit").

Screenshot

Figure - Load Exchange.

"Figure - Load Exchange" shows a successful (violation-free) exchange of two goods, Fruit and Bread. The FruitCapacity before the visit has a load value of 30 and drops the desired 20 items of Fruit at the NodeDepot (therefore, after the visit, the FruitCapacity has a new load value of 30-20 = 10). Or in other words, after visitation, 10 Fruit are left on the truck.

In a PND-Problem a resource, usually, visits multiple customers in the same route. During the Optimization, several different solutions are evaluated. For example, solutions can differ in the visitation-order of the nodes.

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 of 28 "Bread" and maximal capacity of 30.

  1. The first customer (Node A) requests 22 "Bread"; therefore, after visitation, the truck still has 6 "Bread" left.
  2. The subsequent customer (Node B) supplies the resource with 3 "Bread". Afterward, the new capacity value is 9.
  3. The last customer (Node C) requests 12 "Bread". As we have only 9 "Bread" left. We are underloaded, as we can't wholly serve the customer request. However, as the customer, in this example, accepts a fuzzy delivery, we drop the full truck-load of 9 "Bread".

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 to serve the customer request.
  • Underload-NO-MATCH: The ResourceDepot is not available for the good, requested by the customer.

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 CapcityLoad within a ResourceDepot has maximal individual capacity. This value describes the maximal loading of a good, assuming all other loads have a load value of zero. Taking the example from "Figure - Overload Violations", a LoadCapacity with an initial load value of 15 Fruit is requested to take another 20 Fruit. Obviously, 15 + 20 = 35 would exceed the individual capacity of 30 by 5. (Another example would be a truck that has a cold storage room with a particular capacity for a specific type of goods "Meat" installed, that takes up half of the floor-space. In case the cold-room is full, it is not possible to store more units of the "Meat" event though the other half (non-cooled) of the floor space is still empty.)
  • Total overloading: A ResourceDepot has maximal total capacity. This capacity includes all goods a ResourceDepot is allowed to store. For example, taking 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 Fruit is transferred. After the first exchange, the LoadCapacity, now, 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 never drops more goods than it has => The requesting NodeDepot gets fewer goods delivered. Further, a ResourceDepot never takes more goods than it can, defined due to its total and individual capacity limitations => The supplying NodeDepot keeps the goods 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 maximal duration is violated, the solution gets a penalty cost assigned (timing a load is always a soft-constraint). A FlexibleLoad can generate an artificial supply or a request, depending on what is beneficial for the solution of the PND-Problem. A UnloadAllLoad can request all goods of a ResourceDepot.

In the following, we first give an overview of the different load types, before outlining some example use-cases for the different load types, to give a better understanding.

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 case the maximal duration is violated, the solution receives a penalty cost. In case of a violation, an OVERTIME violation is reported.
  • MixedFlex Load: The load value (initially zero or a user-defined hint) is allowed to change as result of the Optimization. The load status (request or supply) is also allowed to change as result of the Optimization.
  • UnloadAll Load: Load value will adjust itself to request one CapacityLoad (or multiple) of a ResourceDepot completely.

Screenshot

Figure - Types of Load.

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

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

Use-Cases for Load Types

For providing a better understanding of how each of the described load types can be utilized, in the following, we give some examples. 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 to each of them that each of the trips would not take more than one hour.

  • Task for the Optimizer: Pickup and deliver each of the passengers within one hour.

Example

Example on GitHub: PNDTimedLoadExample.

Example MixedFlexLoad

A resource has to deliver/pickup "Fridges" and has to deliver/pickup "TVs". Each customer can decide what to pick up (customer supply) and what needs to be delivered (customer request). 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 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.

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

Example

Example on GitHub: PNDMixedFlexLoadExample.

Example RequestFlexLoad

Taken the example from MixedFlexLoad, we assume instead of having a warehouse, we have a only storage capability, meaning we cannot get any loads but can store Loads.

  • 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 SupplyFlexLoad are added where each of them can supply an optimizer-defined value of pieces of bread. The optimized load of each SupplyFlexLoad describes the optimal number of pieces of bread each bakery has to prepare, what can be used for production planning.

(For an overview description of this problem 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. On every customer order, the restaurants can decide which restaurant is serving the request.

The restaurant chain advertises with: "If you don't get your pizza in 90 minutes, you get if for free!". Therefore, each pizza should be delivered within 90 minutes.

Two TimedSupplyFlexLoad are added where each of them can supply several user-defined types of pizza (e.g., "Pizza Margarita" for customer Tom, or "Pizza Mexican" for customer Sophia). The optimized loads (zero or one) of each TimedSupplyFlexLoad describes the pizzas each restaurant has to prepare, what can be used for production planning.

  • 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 "Trash" from customers (customer supply). After visiting a few customers, the ResourceDepot is full. For avoiding overload, multiple different UnloadAllLoads can be visited to unload "Trash" (request) completely. Here, each UnloadAllLoad acts as a waste disposal site. Each UnloadAllLoad is bound to a separate NodeDepot of a separate optional node.

Info

An unloadAllLoad can also be designed by using a Mixed- or RequestFlexLoad. However, in case 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 another load. However, in reality, some loads require more space than other loads. 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 to pick up (customer supply) and what needs to be delivered (customer request).

It is evident that a truck can load more units of cups than units of Pianos. Let's assume the cups are transported on pallets with a size of 1219 x 1016 mm. We do not allow to stack the pallets as otherwise, cups could break. Each customer is only allowed to request or provide pallets of cups. A piano has a floor space of 160 x 140 cm. Obviously, we cannot stack pianos as well (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, what is the maximal amount of both goods, a truck can carry without overloading. For this, we have to calculate the equivalent of one piano, and one pallet of cups.

Precisely, we think of a ground unit with the value one (for cargo space, this is square-meters). 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 individual load describes the maximal loading of a particular type of goods 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 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. Meaning we can either load 4 Pianos or 10 pallets of cups. However, what if we have to load 2 Pianos and 6 pallets of cups? Are we already overloaded? For finding out, we have to relate pianos and pallets of cups to a ground unit defined by the truck. This relation is established by calculating the CapacityFactors for piano and pallets of cups.

Calculating the Capacity Factors

In the following we calculate this CapacityFactors based on the trucks 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 itself 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. In the following, 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: What is the initial load we start with, and what is the final load after the Resource is done with the route. (One report per route)
  • NodeDepot-Report: What is the desired exchange before being visited, and what is the desired exchange after being visited. (One report per node per route)

ResourceDepot-Report

In the following, we first analyze the ResourceDepot-Report. For this purpose, we have a look at the architecture of the report:

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

  1. START: What are the properties of the ResoruceDepot BEFORE we start the route.
  2. TERMINATION: What are the properties of the ResoruceDepot 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 result is 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:

  1. Properties of the ResourceDepot:
    • Id: The id of the ResourceDepotId. (e.g. "JackTruckCologneDepot")
    • Type: The type of the ResourceDepot. (e.g. "SimpleResourceDepot")
    • MaxTotalCapacity: The maximal total capacity, including all loads. (e.g. "20")
    • UsedCapacity: The currently used total capacity, including all loads. (e.g., "0" if there is no loading)
  2. Properties of LoadCapacities:
    • (n) LoadCapacity: The nth index of the LoadCapacity inside the ResoruceDepot. (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 load Capacity. (e.g. "20")

The full report (unformatted), for example, looks like the following:

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

In the following, we 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 describes 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 result is formatted 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 load-value should be exchanged? For example, a value of 7 Bread needs to be delivered.
    • IsRequest: Does the load request goods (true), or does the load provide goods (false)?
    • IsFuzzy: Is it allowed only to deliver/pick-up goods partially?
    • Priority: In case multiple loads are visited, nodes 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
        ]

In this example, we were able to serve the requested 7 units of Bread. Therefore, before the visit, we have a request of 7, and after the visit (after the exchange), we have a request of 0. For example, in case the ResourceDepot would not be able to serve 7 units (for example, only 5 units because of underloading), the NodeDepot would be left with a remaining desired request of 2.


Closing Words

The outlined concept is in beta-status. Therefore, this document and the outlined concepts may change as part of the development process.


Authors

A product by dna-evolutions ©