Construction heuristic for SDCVRP

I'm not sure how I should formulate this question as precisely as possible but at the same time retaining as much specific information as possible but I'll have a go.

I have implemented a (Split Delivery Capacitated Vehicle Routing Problem) SDCVRP model for picking operations in a warehouse. That is, customers to be visited are replaced by pick locations to be picked.

The model has the following sets, parameters and variables:

1. $$x_{ijk}$$ is the indicator of travel from $$i$$ to $$j$$ by forklift $$k$$.
2. $$v_{ik}$$ is the positive integer variable indicating how many items
3. $$y_{ik}$$ is the indicator of visit of $$i$$ by forklift $$k$$. forklift $$k$$ picks up at location $$i$$. (Each location has a distinct item).
4. $$u_{ik}$$ a dummy variable used in the MTZ subtour elimination constraints.
5. $$\mathcal{N}_0$$ is the set of all locations, including the depot.
6. $$\mathcal{N}$$ is the set of all pick-locations, excluding the depot.
7. $$\mathcal{K}$$ is the set of all forklifts.
8. $$d_{i}$$ is the demand at location $$i$$. I.e, total number of items $$i$$ to be picked.
9. $$w_{i}$$ is the weight of item at location $$i$$.
10. $$z_{i}$$ is the volume of item at location $$i$$.
11. $$W$$ is the maximum weight capacity of each forklift.
12. $$V$$ is the maximum volume capacity of each forklift.

The mathematical model is formulated as follows.

\begin{align} % objective \min_{\boldsymbol{x}, \ (i,j)\in \mathcal{E}, \ k\in\mathcal{K}} \quad & z=\displaystyle\sum_{k\in\mathcal{K}}\displaystyle\sum_{i\in\mathcal{N}_0}\displaystyle\sum_{j\in\mathcal{N}_0}c_{ij}x_{ijk} \\ \nonumber\\ % constraints \textrm{subject to} \quad & \displaystyle\sum_{i\in\mathcal{N}_0 \\ i\neq p}x_{ipk} - \displaystyle\sum_{i\in\mathcal{N}_0 \\ j\neq p}x_{pjk} = 0, & p\in \mathcal{N},\quad k\in\mathcal{K} \tag{1}\\ &u_{ik}+1-|\mathcal{N}_0|(1-x_{ijk}) \le u_{jk}, & i,j\in \mathcal{N}, \quad k\in\mathcal{K} \tag{2}\\ &d_{i}y_{ik} \ge v_{ik}, & i\in \mathcal{N}, \quad k\in\mathcal{K} \tag{3}\\ &\sum_{j\in\mathcal{N}_0 \\ j\neq i}x_{ijk} = y_{ik}, & i \in \mathcal{N}, \quad k\in\mathcal{K} \tag{4}\\ &y_{ik} \leq v_{ik}, & i\in \mathcal{N}, \quad k\in\mathcal{K} \tag{5}\\ &\sum_{j\in\mathcal{N}_0 \\ j\neq i}d_ix_{ijk} \ge v_{ik}, & i \in \mathcal{N}, \quad k\in\mathcal{K} \tag{6}\\ & \displaystyle\sum_{k\in\mathcal{K}} v_{ik} = d_i, & i\in\mathcal{N} \tag{7}\\ & \displaystyle\sum_{i\in\mathcal{N}} v_{ik}w_i \le W, & k\in\mathcal{K} \tag{8}\\ & \displaystyle\sum_{i\in\mathcal{N}} v_{ik}z_i \le V, & k\in\mathcal{K} \tag{9}\\ & x_{ijk} \in \{0,1\}, & i,j\in \mathcal{N}_0, \quad k\in\mathcal{K} \tag{10}\\ & v_{ik} \in \mathbb{Z}^{+}, & i\in\mathcal{N}, \quad k\in\mathcal{K} \tag{11}\\ & y_{ik} \in \{0,1\}, & i\in\mathcal{N}, \quad k\in\mathcal{K} \tag{12}\\ & u_{ik} \in \mathbb{Z}^{+}, & i\in\mathcal{N}, \quad k\in\mathcal{K} \tag{13} \end{align}

where $$(1)$$ is the flow conservation constraints, $$(2)$$ are the subtour elimination constraints, $$(3),(4)$$ force the binary variables to be positive if material is delivered to node $$i$$ on route $$k$$. Constraint $$(5)$$ guarantees that if a customer is visited then material is delivered, and Constraint $$(6)$$ does not allow material to be delivered unless a customer is visited. Constraints $$(7)$$ enforce that the combined load of all forklifts that pick at $$i$$ should equal the demand at location $$i$$. Constraints $$(8),(9)$$ enforce max volume and max weight capacity while constraints $$(10)-(13)$$ specify the variables.

I've implemented this model in Gurobipy and upon running it with $$|\mathcal{K}|=5$$ forklifts and $$|\mathcal{N}_0|=10$$ pick locations for 10 minutes I get down to 18.9% gap and the following is printed out:

Time limit reached
Best objective 1.220180000000e+03, best bound 9.900500000000e+02, gap 18.8603%
--------------------------------------------------------
Forklift 1 is not used!
--------------------------------------------------------
Forklift 2 route:    Start -> 5 -> Stop
--------------------------------------------------------
--------------------------------------------------------
Forklift 3 route:    Start -> 4 -> 3 -> 6 -> 7 -> 1 -> Stop
Weight loads:       [76, 20, 176, 184, 39] kg        Total weight load: 495 kg
Volume loads:       [334, 372, 816, 1696, 153] m^3       Total volume load: 3371 m^3
--------------------------------------------------------
--------------------------------------------------------
Forklift 4 route:    Start -> 8 -> 2 -> Stop
--------------------------------------------------------
--------------------------------------------------------
Forklift 5 route:    Start -> 4 -> 9 -> 10 -> Stop
--------------------------------------------------------
--------------------------------------------------------
Fleet weight capacity:   2000   kg
Fleet volume capacity:   20000  m^3
Nr fork lifts used:  4


Needless to say, the model performs quite bad when increasing the number of pick locations so I want to develop some heuristic that solves it fast without sacrificing too much optimality. I've looked at this paper by Wilk and Cavalier, however I'm struggling to understand how this heuristic should be implemented. In section 3 the authors state:

The heuristic procedure presented in this section constructs a set of feasible solutions to the SDVRP. The first procedure of the heuristic initializes the input. The second procedure assigns customers to vehicle routes, iteratively. The order of each route is then determined by a traveling salesman problem (TSP) solution procedure, finalizing the solution.

Does this mean that I should use my model above to obtain initial routes, and then switch around stuff randomly till I get a better solution? Seems very trivial and not so efficient.

Also, doesn't solving the TSP also need some heuristic procedure as the number of sub tour elimination constraints increase exponentially?

Given my model, how can I implement the heuristic suggested in this paper? Are there simpler heuristics for the SDCVRP that might be based on other heuristics for the CVRP?

• Constraints (3) and (4) imply that each pick location $i$ is visited exactly once by exactly one forklift, which has to grab the entire demand $d_i.$ Is that intentional?
– prubin
Aug 24, 2022 at 21:30
• I don't see any reason to constraint $u_{i,k}$ to be integer, although it may not hurt (empirical question). Is there any reason you wrote (2) the way you did, rather than $u_{ik} + 1 - \vert N_0\vert (1 - x_{ijk}) \le u_{jk}?$ I think that would provide tighter lower bounds.
– prubin
Aug 24, 2022 at 21:41
• I've never heard of the journal in which this paper has been published. Note that the solutions of their constructive heuristic are not that good either. Actually, it's pretty hard to get a good pure constructive heuristic for routing problems. Approaches yielding good solutions are usually based on local search. And indeed, in the paper, the conclusion is to use the heuristic as a starting solution of a local search algorithm Aug 25, 2022 at 6:03
• @prubin - Correct, I've implemented the correct model, but I missed to include a few things in the model above and some minor typos creeped in. I've now edited my post with corrections so forklifts can visit the same location and split demands. For the $u_{ik}$, I've now let it be continuous but no with noticable improvement. Also, I've implemented the subtour constraints exactly as you wrote it. Please check my updated post. Aug 25, 2022 at 10:09
• @fontanf - Do you know of any sources with examples of local search implementations for cVRP in python? Aug 25, 2022 at 10:26

I don't think you would be using your model when applying the cited heuristic. The heuristic starts by having you assign customers (here, pick locations) to routes in a heuristic manner. There is no optimization model used for the assignment, just one of a number of alternative heuristic rules. Once customers are assigned to routes, the sequencing of each route is determined by solving a TSP. Presumably, in your case, "route" equates to "forklift".

As far as TSPs requiring a heuristic procedure, optimal solutions can be found for fairly large TSPs, larger than you are likely to encounter in your problem (unless you have thousands of pick locations). A key question is how much computational time you are willing to spend on each route. The Concorde TSP solver has solved a problem with 85,900 nodes to optimality, although I don't know what the computation time was. (I'm guessing it was not trivial.)

In any event, since the route partitioning step was a heuristic, you might be happy with a heuristic solution to each TSP problem.

• Thank you for this answer, cleared up a lot of things for me. Before I accept this answer however I got one last question mark. I'm actually following the steps in the paper to implement the heuristic but I'm stuck at page 157, end of first paragraph just below step 2: ”Otherwise, from set R, find the two closest nodes to the nodes in set P[k]. Call the closest node i and the next closest node j.” How exactly do you interpret this? Is it two nodes in R that are furthest from any single node in P[k] OR two nodes in R that are furthest from the centroid of the nodes in P[k]? Aug 29, 2022 at 18:58
• I see that I wrote furthest in the comment above, should be closest of course. Aug 29, 2022 at 19:14
• I would interpret it to mean that you find, for each node not in $P_k,$ the node in $P_k$ nearest to that node, and select the two nodes not in $P_k$ for which those distances are minimal. It is not assumed (nor required) that the closest node in $P_k$ to $i$ is the same as the closest node in $P_k$ to $j.$
– prubin
Aug 29, 2022 at 19:39
• An example: So $(\text{not in} \ P_k) \ \Leftrightarrow \ (\text{in} \ R)$. Assume $R=[1,2,3]$ and $P_k=[4,5,6]$. I calculate the distances $d(1,4), d(2,4), d(3,4), d(1,5), d(2,5), d(3,5), d(1,6), d(2,6), d(3,6)$ and choose the two nodes in $R$ that give me the minimum of the above distances? Aug 30, 2022 at 7:11
• You compute $\delta_m = \min_{n \in \lbrace 4,5,6 \rbrace} d(m,n)$ for $m\in \lbrace 1,2,3 \rbrace$ and then choose the two smallest values of $\delta_m.$
– prubin
Aug 30, 2022 at 15:35