Construction heuristic for SDCVRP

Question

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
Qty loads:          [2] pcs          total load:    2
Weight loads:       [72] kg          Total weight load: 72 kg
Volume loads:       [704] m^3        Total volume load: 704 m^3
--------------------------------------------------------
--------------------------------------------------------
Forklift 3 route:    Start -> 4 -> 3 -> 6 -> 7 -> 1 -> Stop
Qty loads:          [2, 2, 8, 8, 3] pcs          total load:    23
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
Qty loads:          [8, 10] pcs          total load:    18
Weight loads:       [232, 250] kg        Total weight load: 482 kg
Volume loads:       [520, 2780] m^3          Total volume load: 3300 m^3
--------------------------------------------------------
--------------------------------------------------------
Forklift 5 route:    Start -> 4 -> 9 -> 10 -> Stop
Qty loads:          [3, 7, 4] pcs        total load:    14
Weight loads:       [114, 238, 136] kg       Total weight load: 488 kg
Volume loads:       [501, 427, 252] m^3          Total volume load: 1180 m^3
--------------------------------------------------------
--------------------------------------------------------
Fleet weight load:       1537   kg
Fleet weight capacity:   2000   kg
Fleet volume load:   8555   m^3
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?

Answer 1

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.