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.


2 Answers 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.

  • $\begingroup$ I may use your second method as my first approach. This will probably allow me more latitude to use tighter or looser constraints on the delivery schedule options available for a given customer. $\endgroup$ Commented Jan 30, 2022 at 18:51
  • $\begingroup$ I'm approaching it somewhat differently than Method 2. I still need the xi variables because they are used elsewhere to contribute to the objective function. However I found a way to ensure the xi values are connected to a unique delivery schedule using Method 2. $\endgroup$ Commented Jan 30, 2022 at 21:59

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.