1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7"""
8The problem is to deliver some orders to several clients with a single truck.
9Each order consists of a given quantity of a product of a certain type.
10A product type is an integer in {0, 1, 2}.
11Loading the truck with at least one product of a given type requires some
12specific installations. The truck can be configured in order to handle one,
13two or three different types of product. There are 7 different configurations
14for the truck, corresponding to the 7 possible combinations of product types:
15 - configuration 0: all products are of type 0,
16 - configuration 1: all products are of type 1,
17 - configuration 2: all products are of type 2,
18 - configuration 3: products are of type 0 or 1,
19 - configuration 4: products are of type 0 or 2,
20 - configuration 5: products are of type 1 or 2,
21 - configuration 6: products are of type 0 or 1 or 2.
22The cost for configuring the truck from a configuration A to a configuration B
23depends on A and B.
24The configuration of the truck determines its capacity and its loading cost.
25A delivery consists of loading the truck with one or several orders for the
26same customer.
27Both the cost (for configuring and loading the truck) and the number of
28deliveries needed to deliver all the orders must be minimized, the cost being
29the most important criterion.
30
31Please refer to documentation for appropriate setup of solving configuration.
32"""
33
34from docplex.cp.model import CpoModel
35from sys import stdout
36
37
38#-----------------------------------------------------------------------------
39# Initialize the problem data
40#-----------------------------------------------------------------------------
41
42# List of possible truck configurations. Each tuple is (load, cost) with:
43# load: max truck load for this configuration,
44# cost: cost for loading the truck in this configuration
45TRUCK_CONFIGURATIONS = ((11, 2), (11, 2), (11, 2), (11, 3), (10, 3), (10, 3), (10, 4))
46
47# List of customer orders.
48# Each tuple is (customer index, volume, product type)
49CUSTOMER_ORDERS = ((0, 3, 1), (0, 4, 2), (0, 3, 0), (0, 2, 1), (0, 5, 1), (0, 4, 1), (0, 11, 0),
50 (1, 4, 0), (1, 5, 0), (1, 2, 0), (1, 4, 2), (1, 7, 2), (1, 3, 2), (1, 5, 0), (1, 2, 2),
51 (2, 5, 1), (2, 6, 0), (2, 11, 2), (2, 1, 0), (2, 6, 0), (2, 3, 0))
52
53# Transition costs between configurations.
54# Tuple (A, B, TCost) means that the cost of modifying the truck from configuration A to configuration B is TCost
55CONFIGURATION_TRANSITION_COST = ((0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 3, 10), (0, 4, 10),
56 (0, 5, 10), (0, 6, 15), (1, 0, 0), (1, 1, 0), (1, 2, 0),
57 (1, 3, 10), (1, 4, 10), (1, 5, 10), (1, 6, 15), (2, 0, 0),
58 (2, 1, 0), (2, 2, 0), (2, 3, 10), (2, 4, 10), (2, 5, 10),
59 (2, 6, 15), (3, 0, 3), (3, 1, 3), (3, 2, 3), (3, 3, 0),
60 (3, 4, 10), (3, 5, 10), (3, 6, 15), (4, 0, 3), (4, 1, 3),
61 (4, 2, 3), (4, 3, 10), (4, 4, 0), (4, 5, 10), (4, 6, 15),
62 (5, 0, 3), (5, 1, 3), (5, 2, 3), (5, 3, 10), (5, 4, 10),
63 (5, 5, 0), (5, 6, 15), (6, 0, 3), (6, 1, 3), (6, 2, 3),
64 (6, 3, 10), (6, 4, 10), (6, 5, 10), (6, 6, 0)
65 )
66
67# Compatibility between the product types and the configuration of the truck
68# allowedContainerConfigs[i] = the array of all the configurations that accept products of type i
69ALLOWED_CONTAINER_CONFIGS = ((0, 3, 4, 6),
70 (1, 3, 5, 6),
71 (2, 4, 5, 6))
72
73
74#-----------------------------------------------------------------------------
75# Prepare the data for modeling
76#-----------------------------------------------------------------------------
77
78nbTruckConfigs = len(TRUCK_CONFIGURATIONS)
79maxTruckConfigLoad = [tc[0] for tc in TRUCK_CONFIGURATIONS]
80truckCost = [tc[1] for tc in TRUCK_CONFIGURATIONS]
81maxLoad = max(maxTruckConfigLoad)
82
83nbOrders = len(CUSTOMER_ORDERS)
84nbCustomers = 1 + max(co[0] for co in CUSTOMER_ORDERS)
85volumes = [co[1] for co in CUSTOMER_ORDERS]
86productType = [co[2] for co in CUSTOMER_ORDERS]
87
88# Max number of truck deliveries (estimated upper bound, to be increased if no solution)
89maxDeliveries = 15
90
91
92#-----------------------------------------------------------------------------
93# Build the model
94#-----------------------------------------------------------------------------
95
96# Create CPO model
97mdl = CpoModel()
98
99# Configuration of the truck for each delivery
100truckConfigs = mdl.integer_var_list(maxDeliveries, 0, nbTruckConfigs - 1, "truckConfigs")
101# In which delivery is an order
102where = mdl.integer_var_list(nbOrders, 0, maxDeliveries - 1, "where")
103# Load of a truck
104load = mdl.integer_var_list(maxDeliveries, 0, maxLoad, "load")
105# Number of deliveries that are required
106nbDeliveries = mdl.integer_var(0, maxDeliveries)
107# Identification of which customer is assigned to a delivery
108customerOfDelivery = mdl.integer_var_list(maxDeliveries, 0, nbCustomers, "customerOfTruck")
109# Transition cost for each delivery
110transitionCost = mdl.integer_var_list(maxDeliveries - 1, 0, 1000, "transitionCost")
111
112# transitionCost[i] = transition cost between configurations i and i+1
113for i in range(1, maxDeliveries):
114 auxVars = (truckConfigs[i - 1], truckConfigs[i], transitionCost[i - 1])
115 mdl.add(mdl.allowed_assignments(auxVars, CONFIGURATION_TRANSITION_COST))
116
117# Constrain the volume of the orders in each truck
118mdl.add(mdl.pack(load, where, volumes, nbDeliveries))
119for i in range(0, maxDeliveries):
120 mdl.add(load[i] <= mdl.element(truckConfigs[i], maxTruckConfigLoad))
121
122# Compatibility between the product type of an order and the configuration of its truck
123for j in range(0, nbOrders):
124 configOfContainer = mdl.integer_var(ALLOWED_CONTAINER_CONFIGS[productType[j]])
125 mdl.add(configOfContainer == mdl.element(truckConfigs, where[j]))
126
127# Only one customer per delivery
128for j in range(0, nbOrders):
129 mdl.add(mdl.element(customerOfDelivery, where[j]) == CUSTOMER_ORDERS[j][0])
130
131# Non-used deliveries are at the end
132for j in range(1, maxDeliveries):
133 mdl.add((load[j - 1] > 0) | (load[j] == 0))
134
135# Dominance: the non used deliveries keep the last used configuration
136mdl.add(load[0] > 0)
137for i in range(1, maxDeliveries):
138 mdl.add((load[i] > 0) | (truckConfigs[i] == truckConfigs[i - 1]))
139
140# Dominance: regroup deliveries with same configuration
141for i in range(maxDeliveries - 2, 0, -1):
142 ct = mdl.logical_and([(truckConfigs[p] != truckConfigs[i - 1]) for p in range(i + 1, maxDeliveries)])
143 mdl.add((truckConfigs[i] == truckConfigs[i - 1]) | ct)
144
145# Objective: first criterion for minimizing the cost for configuring and loading trucks
146# second criterion for minimizing the number of deliveries
147cost = sum(transitionCost) + sum(mdl.element(truckConfigs[i], truckCost) * (load[i] != 0) for i in range(maxDeliveries))
148mdl.add(mdl.minimize_static_lex([cost, nbDeliveries]))
149
150# Search strategy: first assign order to truck
151mdl.set_search_phases([mdl.search_phase(where)])
152
153
154#-----------------------------------------------------------------------------
155# Solve the model and display the result
156#-----------------------------------------------------------------------------
157
158# Solve model
159print("\nSolving model....")
160msol = mdl.solve(TimeLimit=20, LogPeriod=3000)
161
162# Print solution
163if msol.is_solution():
164 print("Solution: ")
165 ovals = msol.get_objective_values()
166 print(" Configuration cost: {}, number of deliveries: {}".format(ovals[0], ovals[1]))
167 for i in range(maxDeliveries):
168 ld = msol.get_value(load[i])
169 if ld > 0:
170 stdout.write(" Delivery {:2d}: config={}".format(i,msol.get_value(truckConfigs[i])))
171 stdout.write(", items=")
172 for j in range(nbOrders):
173 if (msol.get_value(where[j]) == i):
174 stdout.write(" <{}, {}, {}>".format(j, productType[j], volumes[j]))
175 stdout.write('\n')
176else:
177 stdout.write("Solve status: {}\n".format(msol.get_solve_status()))