PTSP Example

This web page provide a full description of an PTSP example with a solution build step-by-step to illustrate the article:

Philippe Lacomme, Aziz Moukrim, Alain Quilliot, Marina Vinot. TSupply Chain Optimization with both Production and Transportation Integration: Multiple Vehicles for a Single Perishable Product. International Journal of Production Research. Accepted article

• The example:

Let us consider one instance with 6 customers, 2 vehicles with a a production speed equal to 1, a capacity Q equal to 10 and a product lifespan B equal to 20 (Table 0). Table 1 provides the distance matrix, assuming a directed network (depot is numbered as 0).

Table 0:

Instances:	Number of customers	Customers' demands qi	Number of vehicles	Capacity of vehicles Q	Lifespan of the product B
Example	6	{3;4;2;6;5;3}	3	10	20

Table 1:Distance matrix between customers

/	0	1	2	3	4	5	6
0	0	10	15	5	10	5	10
1	10	0	10	10	30	20	20
2	15	10	0	25	30	20	10
3	5	10	25	0	10	15	20
4	10	30	30	10	0	10	15
5	5	20	20	15	10	0	10
6	10	20	10	20	15	10	0

To build a PTSP solution from the data of the problem, three steps are required:

• to define subsets of customers, in order to define jobs composed of one production and one transportation operation with associated durations;

• to order the jobs created in the first step, in order to define the order of the production and transportation operations;

• to assign a vehicle to each job created in the first step, in order to favour the scheduling of transportation operations in parallel.

First step:

Creation of the jobs by taking the customer in ascending numerical order and with respect to the capacity constraint and the lifespan of the product. Job 1 ← Customer 1       (q₁ ≤ Q and t_0,1 ≤ B) ≡ (3 ≤ 10 and 10 ≤ 20)   true
Job 1 ← Customer 1 + Customer 2       (q₁ + q₂ ≤ Q and t_0,1 + t_1,2 ≤ B) ≡ (7 ≤ 10 and 20 ≤ 20)   true
Job 1 ← Customer 1 + Customer 2 + Customer 3       (q₁ + q₂ + q₃ ≤ Q and t_0,1 + t_1,2 + t_2,3 ≤ B) ≡ (9 ≤ 10 and 45 ≤ 20)   false
Job 2 ← Customer 3       (q₃ ≤ Q and t_0,3 ≤ B) ≡ (2 ≤ 10 and 5 ≤ 20)   true
Job 2 ← Customer 3 + Customer 4       (q₃ + q₄ ≤ Q and t_0,3 + t_3,4 ≤ B) ≡ (8 ≤ 10 and 15 ≤ 20)   true
Job 2 ← Customer 3 + Customer 4 + Customer 5       (q₃ + q₄ + q₅ ≤ Q and t_0,3 + t_3,4 + t_4,5 ≤ B) ≡ (13 ≤ 10 and 25 ≤ 20)   false
Job 3 ← Customer 5       (q₅ ≤ Q and t_0,5 ≤ B) ≡ (5 ≤ 10 and 5 ≤ 20)   true
Job 3 ← Customer 5 + Customer 6       (q₅ + q₆ ≤ Q and t_0,5 + t_5,6 ≤ B) ≡ (8 ≤ 10 and 15 ≤ 20)   true

Three jobs have been created:
Job 1 ← Customer 1 + Customer 2       with q_tot = 7 ≤ Q    t_{last_customer} = 20 ≤ B    and    t_{tot_trip} = 35
Job 2 ← Customer 3 + Customer 4       with q_tot = 8 ≤ Q    t_{last_customer} = 15 ≤ B    and    t_{tot_trip} = 25
Job 3 ← Customer 5 + Customer 6       with q_tot = 8 ≤ Q    t_{last_customer} = 15 ≤ B    and    t_{tot_trip} = 25

The duration of the production operations and of the transportation operations associated are respectively equal to q_tot and t_{tot_trip}.

Second step:

The ascending numerical order can be choose to order the jobs. The scheduling order is then Job 1, Job 2, Job 3.

Third step:

The assignment of the vehicle to each job can be generated randomly. The following assignment can be choose :
Vehicle 1 ← Job 1 + Job 3
Vehicle 2 ← Job 2

Solution representation:

The solution obtained at the end of these steps is represented on Fig. 1 with a semi-active schedule.

Fig 1: Final solution of the example