Integer Programming Constraints - Min/Max Days Between Deliveries

Question

I'm starting a consulting project for a client who manufacturers perishable food. They want to optimize their delivery schedule to each of their DSD (Direct Store Delivery) customers.

For each store, I have binary decision variables that reflect whether I make a delivery to that store on Sunday, Monday, Tuesday, ... Saturday.

e.g., x1 = binary, 1 if I make a delivery on Sunday, 0 if I don't x2 = binary, 1 if I make a delivery on Monday, 0 if I don't ... x7 = binary, 1 if I make a delivery on Saturday, 0 if I don't

Based upon the store's demand, I may want to deliver 1x weekly, 2x weekly, 3x weekly, or 4x weekly. I can set that delivery frequency up as a constraint on the sum of the binaries, but I am having trouble with ensuring spacing of delivery days to ensure the perishable food doesn't spoil on the store shelf.

For example, if I am delivering 2x per week, having delivery days that are consecutive or only spaced by one day in between - Tuesday and Wednesday, or Saturday and Monday - shouldn't be allowed.

For 2x weekly deliveries, I'd like there to be a 3 day gap and a 4 day gap between delivery days: e.g., Sunday & Wednesday; or Friday & Monday.

For 3x weekly deliveries, I'd like there to be at most a 3 day gap between delivery days (Monday & Thursday = 3 day gap). For 4x delivery days, I'd like there to be at most a 2 day gap between delivery days.

I've figured out an (ugly) way to put this constraint together in a 2x weekly delivery schedule, but no idea how to approach for 3x weekly or 4x weekly. Any help is appreciated.

Also FYI, I haven't actually coded anything at this point, just thinking through how I'd approach the problem with pen & paper.

Answer 1

To disallow any given pattern of $0$ and $1$, you can impose "no-good" constraints. For example, if you want to avoid delivering on both Tuesday and Wednesday, that is, avoid $$(x_3,x_4)=(1,1),$$ you want to enforce $$\lnot (x_3 \land x_4).$$ Rewriting in conjunctive normal form yields $$\lnot x_3 \lor \lnot x_4.$$ So the desired constraint is $$(1 - x_3) + (1 - x_4) \ge 1,$$ equivalently, $$x_3+x_4 \le 1.$$

More generally, for any pair $\{i,j\}$ of days that cannot both have a delivery, impose the "conflict" constraint $x_i+x_j \le 1$. The model in the linked answer here strengthens these conflict constraints to "clique" constraints.

Answer 2

Here are two approaches, neither guaranteed to be ideal.

Method 1: Create a new set of binary variables $y_1,\dots,y_4$ signaling how many deliveries per week (1 to 4). Add the constraints $$y_1 + \dots + y_4 = 1$$and $$x_1 + \dots + x_7 = y_1 + 2y_2 + 3y_3 +4y_4.$$ To enforce your gap rules for two deliveries, add constraints $$x_i + x_{i + 1} + x_{i + 2} \le 3 - 2 y_2$$ for all relevant $i$. To enforce your gap rules for three deliveries, use $$x_i + x_{i + 1} + x_{i + 2} + x_{i + 3} \ge 2f_3.$$ Enforcing gap rules for four deliveries is left to the reader as an exercise.

Method 2: Rather than using your $x_i$ variables, generate all possible delivery schedules for a week (Monday only; Monday and Thursday; Monday Tuesday and Thursday; etc.) and use a binary variable for each one to select which will be used. Only include schedules that meet your gap criteria. If this results in too many binary variables, use either branch-and-price or a column generation heuristic.