To speed up real world delivery, it is possible to add intermediate sortation\n", "centers between the fulfillment center and the end customer. The transportation\n", "problem with sortation centers essentially solves the same problem as\n", "crossdocking does. A popular user of this technique is Amazon.com.
\n", "\n", "A set of\n", "fulfillment centers $N$ is supposed to ship products to a set of demand nodes\n", "$M$. The transportation to each of the customers $m$ shall not be split.\n", "Inbetween the fulfillment centers and customers is a set of sortation centers\n", "$S$ which may receive any number of goods from the fulfillment centers. The\n", "actual last mile delivery is done from the sortation centers. The used decision\n", "variables are
\n", "This problem's parameters are
\n", "A straight-forward mixed-integer formulation of this problem is
\n", "\n", "$$\n", "\\begin{align}\n", "\\min \\quad & \\sum_{n \\in N} \\sum_{s \\in S} x_{ns} * c_{ns} + \\sum_{s \\in S} \\sum_{m \\in M} y_{sm} * d_{sm} & \\\\\n", "s.t. \\quad & \\sum_{s \\in S} y_{sm} = 1 & \\forall m \\in M \\\\\n", "& \\sum_{m \\in M} y_{sm} \\cdot u_m = \\sum_{n \\in N} x_{ns} & \\forall s \\in S \\\\\n", "& \\sum_{s \\in S} x_{ns} \\leq u_n & \\forall n \\in N\n", "\\end{align}\n", "$$\n", "In the above model, the objective function minimizes the cost of fulfilling all customer orders. The first constraint set ensures that all customer orders are fulfilled with a single delivery. The next set guarantees that the correct amount of goods are shipped to each sortation center. Finally, the last constraint set ensures that the fulfillment centers do not run out of goods." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This can be realized in PuLP in a straight-forward way. First load the [input file](https://study.find-santa.eu/data/notebooks/sortation_centers.json) and save it to the same directory as this notebook." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import json\n", "with open('sortation_centers.json', encoding='utf-8') as f:\n", " json_pb = json.load(f)\n", "print(json_pb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In order to make working with the input easier, it is nice to wrap it in a series of classes." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class OptimizationObject(object):\n", " def __str__(self):\n", " return self.name\n", "\n", " def __repr__(self):\n", " return str(self)\n", "\n", " def __lt__(self, other):\n", " return self.name < other.name\n", "\n", "\n", "class Customer(OptimizationObject):\n", " def __init__(self, c: dict):\n", " self.name = c['name']\n", " self.demand = c['demand']\n", "\n", "\n", "class FulfillmentCenter(OptimizationObject):\n", " def __init__(self, fc: dict):\n", " self.name = fc['name']\n", " self.supply = fc['supply']\n", "\n", "\n", "class SortationCenter(OptimizationObject):\n", " def __init__(self, sortation_center: dict, fulfillment_centers: dict,\n", " customers: dict):\n", " self.name = sortation_center['name']\n", " self.unit_costs = {fulfillment_centers[fc['from']]: fc['cost']\n", " for fc in sortation_center['unit_cost']}\n", " self.shipping_costs = {customers[cust['to']]: cust['cost']\n", " for cust in sortation_center['shipping_cost']}\n", "\n", "\n", "class Problem(object):\n", " def __init__(self, filename):\n", " self.instance = filename\n", " with open(filename, encoding='utf-8') as f:\n", " json_pb = json.load(f)\n", " self.__customers = {}\n", " for c_dict in json_pb['customers']:\n", " self.__customers[c_dict['name']] = Customer(c_dict)\n", " self.__fulfillment_centers = {}\n", " for fc_dict in json_pb['fulfillment_centers']:\n", " self.__fulfillment_centers[fc_dict['name']] = FulfillmentCenter(\n", " fc_dict)\n", " self.__sortation_centers = {}\n", " for sc_dict in json_pb['sortation_centers']:\n", " self.__sortation_centers[sc_dict['name']] = SortationCenter(\n", " sc_dict, self.__fulfillment_centers, self.__customers)\n", "\n", " def customer(self, name):\n", " return self.__customers[name]\n", "\n", " @property\n", " def customers(self):\n", " return self.__customers.values()\n", "\n", " def fulfillment_center(self, name):\n", " return self.__fulfillment_centers[name]\n", "\n", " @property\n", " def fulfillment_centers(self):\n", " return self.__fulfillment_centers.values()\n", "\n", " def sortation_center(self, name):\n", " return self.__sortation_centers[name]\n", "\n", " @property\n", " def sortation_centers(self):\n", " return self.__sortation_centers.values()\n", "\n", " def __str__(self):\n", " return ('''Transportation Problem with Sortation Centers ({})\n", "{} customers\n", "{} fulfillment_centers\n", "{} sortation_centers'''.format(self.instance, len(self.customers),\n", " len(self.fulfillment_centers),\n", " len(self.sortation_centers)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can look at the input data again." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p = Problem('sortation_centers.json')\n", "print(p)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(p.customers)\n", "print(p.fulfillment_centers)\n", "print(p.sortation_centers)\n", "print(p.sortation_center('Germany').unit_costs)\n", "print(p.sortation_center('Germany').shipping_costs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementing the MILP in PuLP" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's start by declaring the variables." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x_ns = pulp.LpVariable.dicts('x_%s_%s',\n", " (p.fulfillment_centers, p.sortation_centers),\n", " cat=pulp.LpInteger, lowBound=0)\n", "y_sm = pulp.LpVariable.dicts('y_%s_%s',\n", " (p.sortation_centers, p.customers),\n", " cat=pulp.LpBinary)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can declare the problem." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp = pulp.LpProblem('Transportation Problem with Sortation Centers',\n", " pulp.LpMinimize)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We use PuLP's `pulp.lpSum` for improved performance over the regular general purpose `sum`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pulp import lpSum" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The objective function as well as constraints are added with Python's `+=` Syntax. The objective is to minimize the overall shipping cost, i.e. the sum of the shipping cost from fullfillment centers $N$ to sortation centers $S$ and from sortation centers $S$ to demand nodes (customers) $M$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\min \\sum_{n \\in N} \\sum_{s \\in S} x_{ns} * c_{ns} + \\sum_{s \\in S} \\sum_{m \\in M} y_{sm} * d_{sm}\n", "$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp += (lpSum(x_ns[n][s] * s.unit_costs[n] for n in p.fulfillment_centers\n", " for s in p.sortation_centers) +\n", " lpSum(y_sm[s][m] * s.shipping_costs[m]\n", " for s in p.sortation_centers for m in p.customers),\n", " 'objective function')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first constraint set we add ensures that all customer orders $M$ are fulfilled with a single delivery." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\sum_{s \\in S} y_{sm} = 1,\\quad \\forall m \\in M$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for m in p.customers:\n", " milp += (lpSum(y_sm[s][m] for s in p.sortation_centers) == 1,\n", " '{}'.format(m))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's look at what the problem looks like at this stage." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can add the second constraint set and look at the problem again. This set guarantees that the correct amount of goods are shipped to each sortation center." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\sum_{m \\in M} y_{sm} \\cdot u_m = \\sum_{n \\in N} x_{ns} \\quad \\forall s \\in S$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for s in p.sortation_centers:\n", " milp += (lpSum(x_ns[n][s] for n in p.fulfillment_centers) ==\n", " lpSum(y_sm[s][m] * m.demand for m in p.customers),\n", " '{}'.format(s))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we add the last constraint set which ensures that the fulfillment centers $N$ do not run out of goods." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\sum_{s \\in S} x_{ns} \\leq u_n \\quad \\forall n \\in N$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in p.fulfillment_centers:\n", " milp += (lpSum(x_ns[n][s] for s in p.sortation_centers) <= n.supply,\n", " '{}'.format(n))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have a complete MILP object that represents a working model, we can either solve it or export it to an LP or MPS file." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "milp.solve()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Looking at the \"raw\" solution is impractical and hard to read for larger problems." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for var in milp.variables():\n", " print('{}: {}'.format(var.name, var.value()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is hence recommendable to parse the variable values in a easy to work with solution object. Of course, this only really pays off when working with many the same problem multiple times." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Solution(object):\n", " def __init__(self, p: Problem, milp: pulp.LpProblem):\n", " self.instance = p.instance\n", " assert (milp.status == pulp.LpStatusNotSolved or\n", " milp.status == pulp.LpStatusOptimal), \"problem is {}\".format(\n", " pulp.LpStatus[milp.status])\n", " self.value = milp.objective.value()\n", " self.DCtoSC = {fc: {sc: 0 for sc in p.sortation_centers}\n", " for fc in p.fulfillment_centers}\n", " self.SCtoCust = {sc: {c: 0 for c in p.customers}\n", " for sc in p.sortation_centers}\n", " for var in milp.variables():\n", " if var.name.startswith('x'):\n", " fc = p.fulfillment_center(var.name.split('_')[1])\n", " sc = p.sortation_center(var.name.split('_')[-1])\n", " self.DCtoSC[fc][sc] = var.value()\n", " elif var.name.startswith('y'):\n", " sc = p.sortation_center(var.name.split('_')[1])\n", " c = p.customer(var.name.split('_')[-1])\n", " self.SCtoCust[sc][c] = var.value() * c.demand\n", "\n", " def __str__(self):\n", " dc_to_sc = ''\n", " for key in sorted(self.DCtoSC):\n", " dc_to_sc += '{}: {}\\n'.format(key,\n", " {k: v for k, v in\n", " self.DCtoSC[key].items() if v})\n", " sc_to_cust = ''\n", " for key in sorted(self.SCtoCust):\n", " sc_to_cust += '{}: {}\\n'.format(key,\n", " {k: v for k, v in\n", " self.SCtoCust[key].items() if v})\n", " return 'value: {}\\n\\nDC to SC\\n{}\\nSC to Cust\\n{}'.format(self.value,\n", " dc_to_sc,\n", " sc_to_cust)\n", "\n", " def to_json(self):\n", " def sanitized(d: dict):\n", " return {str(k): {str(ik): iv for ik, iv in v.items()}\n", " for k, v in d.items()}\n", " sol = {'value': self.value,\n", " 'DCtoSC': sanitized(self.DCtoSC),\n", " 'SCtoCust': sanitized(self.SCtoCust)}\n", " return json.dumps(sol, indent=2)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sol = Solution(p, milp)\n", "print(sol)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sol.to_json()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Larger Problems" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "For larger problems it pays off to separate the objective function and the constraint into separate Python functions. This can be done, for example, in the the following way" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def __objective_function(index, p, milp, x_ns, y_sm, **kwargs):\n", " \"\"\"The objective function.\"\"\"\n", " milp += (lpSum(x_ns[n][s] * s.unit_costs[n] for n in p.fulfillment_centers\n", " for s in p.sortation_centers) +\n", " lpSum(y_sm[s][m] * s.shipping_costs[m]\n", " for s in p.sortation_centers for m in p.customers),\n", " '({}) objective function'.format(index))\n", "\n", "\n", "def __constraint_fulfill_deliveries(index, p, milp, y_sm, **kwargs):\n", " \"\"\"Ensure that all customer orders are fulfilled with a single delivery.\"\"\"\n", " for m in p.customers:\n", " milp += (lpSum(y_sm[s][m] for s in p.sortation_centers) == 1,\n", " '({}) {}'.format(index, m))\n", "\n", "\n", "def __constraint_goods_sortation_centers(index, p, milp, x_ns, y_sm, **kwargs):\n", " \"\"\"Ship correct amount of goods to each sortation center\"\"\"\n", " for s in p.sortation_centers:\n", " milp += (lpSum(x_ns[n][s] for n in p.fulfillment_centers) ==\n", " lpSum(y_sm[s][m] * m.demand for m in p.customers),\n", " '({}) {}'.format(index, s))\n", "\n", "\n", "def __constraint_supply_fulfillment_centers(index, p, milp, x_ns, **kwargs):\n", " \"\"\"Ensure that the fulfillment centers do not run out of goods.\"\"\"\n", " for n in p.fulfillment_centers:\n", " milp += (lpSum(x_ns[n][s] for s in p.sortation_centers) <= n.supply,\n", " '({}) {}'.format(index, n))\n", "\n", "\n", "__model = (\n", " __objective_function,\n", " __constraint_fulfill_deliveries,\n", " __constraint_goods_sortation_centers,\n", " __constraint_supply_fulfillment_centers\n", ")\n", "\n", "def model(p: Problem):\n", " \"\"\"\n", " Return the MILP model for the\n", "\n", " TODO: split up into separate functions\n", " \"\"\"\n", " x_ns = pulp.LpVariable.dicts('x_%s_%s',\n", " (p.fulfillment_centers, p.sortation_centers),\n", " cat=pulp.LpInteger, lowBound=0)\n", " y_sm = pulp.LpVariable.dicts('y_%s_%s',\n", " (p.sortation_centers, p.customers),\n", " cat=pulp.LpBinary)\n", " # declare problem\n", " milp = pulp.LpProblem('Transportation Problem with Sortation Centers',\n", " pulp.LpMinimize)\n", " for index, equations in enumerate(__model, 1):\n", " equations(**locals())\n", " return milp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This allows separately testing each constraint and adding / removing constraint sets without losing oversight over the entire model. Obtaining a solution is now limited to the following few lines of code." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p = Problem('sortation_centers.json')\n", "milp = model(p)\n", "milp.solve()\n", "sol = Solution(p, milp)\n", "print(sol)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The complete implementation of the example above is also available for [download](https://study.find-santa.eu/data/py/milp.py). Please note that this is still a very small model which can be solved to optimality for smaller instances. The provided code is overkill for the size of the given problem. However, it nicely shows how\n", "\n", "* objective function and constraints can be placed into separate functions\n", "* the model documentation can be used to generate a dynamic overview of the model\n", "* the solution can be abstracted to allow both human- and machine-readable (json) output\n", "\n", "All of the above techniques are useful when implementing large models. Of course, there is still much more that can be done depending on problem and data size and individual requirements." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Concluding Remarks" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Of course, PuLP allows many more things to be done. For example, it has a good integration of all common open source and commercial solvers. By default, Coin CBC is used, which is the most powerful open source alternative. However, large problems demand using the (at the time of this writing) more powerful commercial alternatives. Eg. Gurobi is roughly 25 times faster than CBC ([Source](http://scip.zib.de/)) and can solve larger instances that cannot be solved by CBC." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.6" } }, "nbformat": 4, "nbformat_minor": 1 }