A project on using mathematical programming to solve multi-modal transportation cost minimization in goods delivery and supply chain management.
A project on using mathematical programming to solve multi-modal transportation cost minimization in goods delivery and supply chain management.
Project Overview
Problem Statement
Assumptions
Dimension & Matrixing
Decision Variables
Parameters
Mathematical Modelling
Optimization Result & Solution
Model Use & Extension Guide
In delivery services, many different transportation tools such as trucks, airplanes and ships are available. Different choices of routes and transporation tools will lead to different costs. To minimize cost, we should consider goods consolidation (Occassions when different goods share a journey together.), different transportation costs and delivery time constraints etc. This project uses mathematical programming to model such situation and solves for overall cost minimization solution. The model construction offers options of two mathematical programming frameworks, DOcplex and CVXPY.
DOcplex is a commercial programming framework developed by IBM, which directly calls the CPLEX solver. If you want to use this framework option, installation of CPLEX Studio needs to be done beforehand. CVXPY is an open-source programming framework originally developed by a Stanford research team, detailed info can be found here. With this option, you can choose from a list of solvers integrated by CVXPY framework, CBC solver (open-source, needs to be installed first) is recommended for this model, details can be seen here.
In our simulated case, there are 8 goods, 4 cities/countries (Shanghai, Wuxi, Singapore, Malaysia), 16 ports and 4 transportation tools. The 8 goods originate from different cities and have different destinations. Each city/country has 4 ports, the airport, railway station, seaport and warehouse. There are in total 50 direct routes connecting different ports. Each route has a specific transportation tool, transportation cost, transit time and weekly schedule. Warehouse in each city allows goods to be deposited for a period of time so as to fit certain transportation schedules or wait for other goods to be transported together. All goods might have different order dates and different delivery deadlines. With all these criteria, how can we find out solution routes for all goods that minimize the overall cost?
(The above diagram is only used to show the basic idea of the problem, the routes are not complete.)
Before model building, some assumptions should be made to simplify the case because real-world delivery problems consist of too many unmeasurable factors that can affect the delivery process and final outcomes. Here are the main assumptions:
In order to make the criteria logic clearer and the calculation more efficient, we use the concept of matrixing to build the necessary components in the model. In our case, there are totally 4 dimensions:
All the variable or parameter matrices to be introduced in the later parts will have one or more of these 4 dimensions.
As mentioned above, we will use the concept of variable matrix, a list of variables deployed in the form of a matrix or multi-dimensional array. In our model, 3 variable matrices will be introduced:
varList1 = model.binary_var_list(portDim * portDim * timeDim * goodsDim,name = 'x')
x = np.array(varList1).reshape(portDim, portDim, timeDim, goodsDim)
varList2 = model.integer_var_list(portDim * portDim * timeDim,name = 'y')
y = np.array(varList2).reshape(portDim, portDim, timeDim)
varList3 = model.binary_var_list(portDim * portDim * timeDim,name = 'z')
z = np.array(varList3).reshape(portDim, portDim, timeDim)
Similar to the decision variables, the following parameter arrays or matrices are introduced for the sake of later model building:
Per Container Cost: C
A 3 dimensional parameter matrix, each dimension representing start port, end port and time. Ci,j,t in the matrix represents the overall transportation cost per container from port i to port j at time t. This overall cost includes handling cost, bunker/fuel cost, documentation cost, equipment cost and extra cost from model data.xlsx. For infeasible route, the cost element will be set to be big M (an extremely large number), making the choice infeasible.
Route Fixed Cost: FC
A 3 dimensional parameter matrix, each dimension representing start port, end port and time. FCi,j,t in the matrix represents the fixed transportation cost to travel from port i to port j at time t, regardless of goods number or volume. For infeasible route, the cost element will be set to be big M as well.
Warehouse Cost: wh
A one dimension array with dimension start port. whi represents the warehouse cost per cubic meter per day at port i. Warehouse cost for ports with no warehouse function (like airport, railway station etc.) is set to be big M.
Transportation Time: T
A 3 dimensional parameter matrix, each dimension representing start port, end port and time. Ti,j,t in the matrix represents the overall transportation time from port i to port j at time t. This overall time includes custom clearance time, handling time, transit time and extra time from model data.xlsx. For infeasible route, the time element will be set to be big M.
Tax Percentage: tax
A one dimension array with dimension goods. taxk represents the tax percentage for goods k imposed by its destination country. If the goods only goes through a domestic transit, the tax percentage for such goods will be set as 0.
Transit Duty: td
A two dimensional matrix, each dimension representing start port and end port. tdi,j represents the transit duty (tax imposed on goods passing through a country) percentage for goods to go from port i to port j. If port i and port j belong to the same country, transit duty percentage is set to be 0. For simplicity purpose, transit duty is set to be equal among all goods. (can be extended easily)
Container Volume: ctnV
A two dimensional matrix, each dimension representing start port and end port. ctnVi,j represents the volume of container in the route from port i to port j.
Goods Volume: V
A one dimension array with dimension goods. Vk represents the volume of goods k.
Goods Value: val
A one dimension array with dimension goods. valk represents the value of goods k.
Order Date: ord
A one dimension array with dimension goods. ordk represents the order date of goods k.
Deadline Date: ddl
A one dimension array with dimension goods. ddlk represents the deadline delivery date of goods k.
Origin Port: OP
A one dimension array with dimension goods. OPk represents the port where goods k starts from.
Destination Port: DP
A one dimension array with dimension goods. DPk represents the port where goods k ends up to be in.
The data of all the above parameter matrices will be imported from model data.xlsx with function transform() and set_param(). For more details, please refer to the codes in multi-modal transpotation.py.
With all the variables and parameters defined above, we can build up the objectives and constraints to form an integer programming model.
The objective of the model is to minimize the overall cost, which includes 3 parts, transportation cost, warehouse cost and tax cost. Firstly, the transportation cost includes container cost and route fixed cost. Container cost equals the number of containers used in each route times per container cost while route fixed cost equals the sum of fixed cost of all used routes. Secondly, the warehouse cost equals all goods' sum of volume times days of storage times warehouse fee per cubic meter per day in each warehouse. Finally, the tax cost equals the sum of import tariff and transit duty of all goods. Mathematic formulation and Python implementation are attached below.
transportCost = np.sum(y*perCtnCost) + np.sum(z*tranFixedCost)
warehouseCost = warehouse_fee(x)[0] #For details ,pleas refer to function warehouse_fee() in code.
taxCost = np.sum(taxPct*kValue) + np.sum(np.sum(np.dot(x,kValue),axis=2)*transitDuty)
model.minimize(transportCost + warehouseCost + taxCost)
model.add_constraints(np.sum(x[OriginPort[k],:,:,k]) == 1 for k in range(goodsDim))
model.add_constraints(np.sum(x[:,DestinationPort[k],:,k]) == 1 for k in range(goodsDim))
model.add_constraints(np.sum(x[:,OriginPort[k],:,k]) == 0 for k in range(goodsDim))
model.add_constraints(np.sum(x[DestinationPort[k],:,:,k]) == 0 for k in range(goodsDim))
for k in range(goodsDim):
for j in range(portDim):
if (j != OriginPort[k]) & (j != DestinationPort[k]):
model.add_constraint(np.sum(x[:,j,:,k])==np.sum(x[j,:,:,k]))
model.add_constraints(np.sum(x[i,:,:,k]) <= 1 for k in range(goodsDim) for i in range(portDim))
model.add_constraints(np.sum(x[:,j,:,k]) <= 1 for k in range(goodsDim) for j in range(portDim))
startTime = np.arange(timeDim).reshape(1,1,timeDim,1)*x
arrTime = startTime + tranTime.reshape(portDim,portDim,timeDim,1)*x
stayTime = np.sum(startTime,axis=(1,2)) - np.sum(arrTime,axis=(0,2))
stayTime[OriginPort,range(goodsDim)] -= OrderDate #ship-out time at origin port should be after order date
stayTime[DestinationPort,range(goodsDim)] = 0 #stay time at destination port is not considered
model.add_constraints(stayTime[i,k] >= 0 for i in range(portDim) for k in range(goodsDim))
numCtn = np.dot(x,kVol) / ctnVol.reshape(portDim,portDim,1)
model.add_constraints(y[i,j,t] - numCtn[i,j,t] >= 0 \
for i in range(portDim) for j in range(portDim) for t in range(dateDim))
model.add_constraints(z[i,j,t] >= np.sum(x[i,j,t,:])*10e-5 \
for i in range(portDim) for j in range(portDim) for t in range(timeDim))
arrTime = np.arange(timeDim).reshape(1,1,timeDim,1)*x + tranTime.reshape(portDim,portDim,timeDim,1)*x
model.add_constraints(np.sum(arrTime[:,DestinationPort[k],:,k]) <= kDDL[k] for k in range(goodsDim))
With the objective & constraints built, the model is now complete! To make users understand the result easier, we process it with the function txt_solution() and save it into a text file Solution.txt. The minimized cost value as well as optimal routes for all goods are presented in it.
Now that you know about all the details of the model, if you want to use it, just download the multi-modal transportation.py & model data.xlsx in this repo. You can reset all the parameters' data in the excel file to fit your own case. After that, just run the python file and your Solution.txt will be generated!
The code is written in OOP format, so you can easily modify or extend the class MMT to fit cases of more complex situations. You can also try modifying the assumptions such as making it to be a stochastic optimization problem or so on.
Finally, hope this long documentation helps, and thanks all my MSBA teammates (Derek, Teng Lei, Max, Veronica, Sophia) for the help and contributions in this project!