python constraints linear-programming or-tools cp-sat

Define constraints with or-tools for a carpooling problem

I am having a real life situation where I am trying to solve a school carpooling problem. I thought it would be good to try and use or-tools and learn in the process.

The school is divided into 2 locations, some children go to location 1 and some to location 2 (for the entire week)

So far, I have defined the model:

from ortools.sat.python import cp_model
def main():
  # Data.
  num_parents = 12
  num_children = 20
  num_days = 5
  num_locations = 2
  all_parents = range(num_parents)
  all_children = range(num_children)
  all_days = range(num_days)
  all_locations = range(num_locations)

  # Creates the model.
  model = cp_model.CpModel()
  # Creates ride variables.
  # rides[(n, d, c, l)]: parent 'n' takes child 'c' on day 'd' to location l.
  rides = {}
  for n in all_parents:
    for d in all_days:
      for c in all_children:
        for l in all_locations:
        rides[(n, d, c, l)] = model.NewBoolVar('ride_n%id%ic%il%i' % (n, d, c, l))

Now I am trying to define the constraints. Here they are:

Each parent can take up to 4 kids in a ride (would be cool to have that number adjustable per parent as some of them have bigger cars, but lets assume 4)
Each parent should only drive to one of the locations during a ride
Maximum 2 rides per parent per day (pickup and drop-off, but can't do more than that)
Parent always drives at least one of their children in a ride (at least one, but not necessarily all of them)
Each child either goes to location 1 or to location 2. It never changes.
I am trying to make it fair so that the work is spread across everyone

Could someone please give me some examples how to model these constraints ? Also, I haven't yet thought of how to model the parent-child relationship in constraint #4 or the child-location relationship in constraints #5

Solution

Interesting problem...

Below is a solution written in pulp which is another framework for linear programs. It is pretty simple framework, doesn't have some of the bells & whistles of or-tools, but most of those (IMHO) are just syntactic sugar for the basics.

Anyhow, a couple of comments on the problem/code...

You say "make it fair" ... but alas, that doesn't have a strict mathematical interpretation. There are many variants. You could implement a weighted scoring system where everybody gives their preferences, etc. I just used a mini-max or minimizing the maximum number of rides given in the time period, which tends to flatten things out. Realize if you use that and repeat over small durations, the differences could add up. So if you do it weekly and the max is 3, but some folks get 2, then when repeated many times ....
You implied that there is drop-off and pick-up but they are not differentiated in any way in the model, so it can be assumed whoever drops off does the pickup.
This runs on my machine for 15 days in about 5 seconds, but goes into overtime at 20 days.... Sometimes there are interesting break points in integer-based problems, so tinker around. This will also obviously depend on the data.
There are a slew of enhancements that might be done to tighten up the formulation and make it a little quicker & slicker, but not too important to get started and might only be considered if the solve time is wayyyy too long.
The "next thing" you probably want to tinker with might be "exclusion days" where you clamp the drive variable to zero (with a constraint) for particular days that are captured in another parameter, indexed by parent.

Code:

from pulp import LpProblem, LpVariable, LpConstraint, LpMinimize, LpBinary, lpSum, LpStatus
from collections import defaultdict

# DATA
parents = [f'p{n}' for n in range(12)]
kids =    [f'k{n}' for n in range(20)]
days = list(range(15))
schools = ['Middle School', 'High School']

# some wrangling to make parameters
school_assignments = dict()
for k in kids[:12]:
    school_assignments[k] = 'Middle School'
for k in kids[12:]:
    school_assignments[k] = 'High School'

# ... model parameters ...
# car sizes
car_size = dict()
car_size.update({p:3 for p in parents[:4]})
car_size.update({p:4 for p in parents[4:9]})
car_size.update({p:6 for p in parents[9:]})   # <- the mini van-ers!
max_passengers = max(car_size.values())

# parent-kid pairs
kids_parents = (
    ('k0', 'p0'),
    ('k1', 'p1'),
    ('k2', 'p1'),
    ('k3', 'p1'),
    ('k4', 'p2'),
    ('k5', 'p2'),
    ('k6', 'p3'),
    ('k7', 'p4'),
    ('k8', 'p4'),
    ('k9', 'p5'),
    ('k10', 'p6'),
    ('k11', 'p7'),
    ('k12', 'p8'),
    ('k13', 'p8'),
    ('k14', 'p9'),
    ('k15', 'p10'),
    ('k16', 'p10'),
    ('k17', 'p10'),
    ('k18', 'p10'),
    ('k19', 'p11'))

# convert the tuples to dict...  could have done this from start, but oh well
parent_dict = defaultdict(set)
for k, p in kids_parents:
    parent_dict[p].add(k)
# print(parent_dict)

# make the model...

prob = LpProblem('carpool', sense=LpMinimize)

# VARIABLES
# pre-bake the index set, it is just a convenience
pksd = {(p, k, s, d) for p in parents for k in kids for s in schools for d in days}
carry = LpVariable.dicts('carry', indices=pksd, cat=LpBinary)

psd = {(p, s, d) for p in parents for s in schools for d in days}
drive = LpVariable.dicts('drive', indices=psd, cat=LpBinary)

max_trips = LpVariable('max_trips')

# OBJ:  minimize the max number of trips across individuals
prob += max_trips   # this just assigns the single variable as the objective and tries to minimize this single variable

# CONSTRAINTS

# 0. capture the max trips per parent to support the obj
for p in parents:
    prob += max_trips >= sum(drive[p, s, d] for s in schools for d in days)

# 1. limit to car capacity...  see the first linking constraint below

# 2.  only one location per parent-trip
for d in days:
    for p in parents:
        prob += sum(drive[p, s, d] for s in schools) <= 1

# linking constraints
for d in days:
    for p in parents:
        for s in schools:
            # don't exceed car capacity
            prob += sum(carry[p, k, s, d] for k in kids) <= car_size[p] * drive[p, s, d]
            # carry at least one of your own if you make the trip...
            prob += sum(carry[p, k, s, d] for k in parent_dict[p]) >= drive[p, s, d]

# 3.  Skipped...  N/A

# 4.  Carry one of your own (see linking constraint)

# 5.  Every kid must make it to (or from) their school every day
for k in kids:
    for d in days:
        prob += sum(carry[p, k, school_assignments[k], d] for p in parents) >= 1

# print(prob)

soln = prob.solve()
assert (LpStatus[prob.status]) == 'Optimal'   # must check that the solve went OK

# for p, k, s, d in sorted(pksd):
#   if carry[p, k, s, d].varValue:
#       print(f'{p} carrys {k} to {s} on {d}')

print(f'the max trips per driver is: {max_trips.varValue}')
for p, s, d in sorted(psd, key=lambda x: (x[2], x[0], x[1])):
    if drive[p, s, d].varValue: 
        carried_kids = {k for k in kids if carry[p, k, s, d].varValue}
        print(f'on day {d} parent {p} carries {carried_kids} to {s}')

Output (partial):

the max trips per driver is: 7.0
on day 0 parent p0 carries {'k18', 'k0', 'k13'} to High School
on day 0 parent p11 carries {'k12', 'k19', 'k15', 'k17', 'k16', 'k14'} to High School
on day 0 parent p3 carries {'k6', 'k3', 'k1'} to Middle School
on day 0 parent p5 carries {'k9', 'k5', 'k0', 'k7'} to Middle School
on day 0 parent p9 carries {'k11', 'k4', 'k10', 'k14', 'k8', 'k2'} to Middle School
on day 1 parent p0 carries {'k0', 'k7', 'k2'} to Middle School
on day 1 parent p1 carries {'k6', 'k1', 'k8'} to Middle School
on day 1 parent p10 carries {'k12', 'k18', 'k15', 'k17', 'k13', 'k14'} to High School
on day 1 parent p3 carries {'k6', 'k16', 'k19'} to High School
on day 1 parent p6 carries {'k9', 'k3', 'k10', 'k5'} to Middle School
on day 1 parent p8 carries {'k11', 'k4', 'k13'} to Middle School
on day 2 parent p11 carries {'k19', 'k3', 'k2'} to Middle School
on day 2 parent p2 carries {'k4', 'k9', 'k10'} to Middle School
on day 2 parent p3 carries {'k6', 'k0', 'k8'} to Middle School
on day 2 parent p4 carries {'k11', 'k5', 'k1', 'k7'} to Middle School
on day 2 parent p8 carries {'k18', 'k16', 'k12', 'k19'} to High School
on day 2 parent p9 carries {'k12', 'k15', 'k17', 'k13', 'k14'} to High School
on day 3 parent p0 carries {'k17', 'k0', 'k19'} to High School
on day 3 parent p4 carries {'k4', 'k7', 'k1', 'k2'} to Middle School
on day 3 parent p5 carries {'k9', 'k3', 'k10', 'k0'} to Middle School
on day 3 parent p7 carries {'k6', 'k5', 'k11', 'k8'} to Middle School
on day 3 parent p9 carries {'k12', 'k18', 'k15', 'k13', 'k16', 'k14'} to High School
on day 4 parent p1 carries {'k10', 'k7', 'k2'} to Middle School
on day 4 parent p10 carries {'k12', 'k19', 'k18', 'k15', 'k17', 'k14'} to High School
on day 4 parent p11 carries {'k9', 'k1', 'k4', 'k5', 'k6', 'k19'} to Middle School
on day 4 parent p4 carries {'k11', 'k3', 'k0', 'k8'} to Middle School
on day 4 parent p8 carries {'k16', 'k12', 'k13'} to High School
on day 5 parent p0 carries {'k15', 'k12', 'k0'} to High School
on day 5 parent p1 carries {'k5', 'k0', 'k2'} to Middle School
on day 5 parent p10 carries {'k19', 'k18', 'k17', 'k13', 'k16', 'k14'} to High School
on day 5 parent p3 carries {'k6', 'k4', 'k8'} to Middle School
on day 5 parent p4 carries {'k3', 'k7'} to Middle School
on day 5 parent p6 carries {'k11', 'k9', 'k10', 'k1'} to Middle School
on day 6 parent p0 carries {'k12', 'k0', 'k14'} to High School
on day 6 parent p1 carries {'k3', 'k5'} to Middle School
on day 6 parent p10 carries {'k18', 'k15', 'k17', 'k13', 'k16', 'k19'} to High School
on day 6 parent p5 carries {'k4', 'k9'} to Middle School
on day 6 parent p6 carries {'k10', 'k0', 'k1', 'k2'} to Middle School
on day 6 parent p7 carries {'k6', 'k11', 'k8', 'k7'} to Middle School
on day 7 parent p10 carries {'k12', 'k19', 'k18', 'k17', 'k13', 'k14'} to High School
on day 7 parent p2 carries {'k4', 'k15', 'k16'} to High School
on day 7 parent p4 carries {'k6', 'k5', 'k1', 'k8'} to Middle School
on day 7 parent p6 carries {'k9', 'k10', 'k0', 'k2'} to Middle School
on day 7 parent p7 carries {'k11', 'k4', 'k3', 'k7'} to Middle School
on day 8 parent p11 carries {'k12', 'k18', 'k15', 'k17', 'k16', 'k19'} to High School
on day 8 parent p2 carries {'k4', 'k10', 'k7'} to Middle School
on day 8 parent p3 carries {'k6', 'k14', 'k13'} to High School
on day 8 parent p4 carries {'k8', 'k0', 'k1', 'k2'} to Middle School
on day 8 parent p7 carries {'k11', 'k9', 'k3'} to Middle School
on day 8 parent p8 carries {'k6', 'k5', 'k12'} to Middle School
on day 9 parent p0 carries {'k11', 'k0', 'k8'} to Middle School
on day 9 parent p10 carries {'k18', 'k3', 'k1', 'k2'} to Middle School
on day 9 parent p2 carries {'k5', 'k10', 'k7'} to Middle School
on day 9 parent p3 carries {'k6', 'k4', 'k9'} to Middle School
on day 9 parent p8 carries {'k18', 'k15', 'k12'} to High School
on day 9 parent p9 carries {'k17', 'k13', 'k16', 'k14', 'k19'} to High School
on day 10 parent p11 carries {'k12', 'k18', 'k17', 'k13', 'k16', 'k19'} to High School
on day 10 parent p2 carries {'k15', 'k5', 'k14'} to High School
on day 10 parent p5 carries {'k4', 'k3', 'k9', 'k2'} to Middle School
on day 10 parent p6 carries {'k5', 'k10', 'k0', 'k8'} to Middle School
on day 10 parent p7 carries {'k6', 'k11', 'k1', 'k7'} to Middle School
on day 11 parent p1 carries {'k7', 'k2'} to Middle School
on day 11 parent p2 carries {'k18', 'k15', 'k5'} to High School
on day 11 parent p3 carries {'k6'} to Middle School
on day 11 parent p5 carries {'k4', 'k5', 'k9', 'k8'} to Middle School
on day 11 parent p6 carries {'k10', 'k0', 'k1'} to Middle School
on day 11 parent p7 carries {'k11', 'k3'} to Middle School
on day 11 parent p9 carries {'k12', 'k19', 'k17', 'k13', 'k16', 'k14'} to High School
on day 12 parent p11 carries {'k19', 'k18', 'k15', 'k17', 'k16', 'k14'} to High School
on day 12 parent p2 carries {'k4', 'k10', 'k0'} to Middle School
on day 12 parent p5 carries {'k6', 'k9', 'k5', 'k8'} to Middle School
on day 12 parent p8 carries {'k12', 'k14', 'k13'} to High School
on day 12 parent p9 carries {'k1', 'k11', 'k2', 'k3', 'k14', 'k7'} to Middle School
on day 13 parent p1 carries {'k6', 'k4', 'k1'} to Middle School
on day 13 parent p11 carries {'k19', 'k5', 'k0', 'k2', 'k10', 'k7'} to Middle School
on day 13 parent p7 carries {'k11', 'k9', 'k3', 'k8'} to Middle School
on day 13 parent p8 carries {'k15', 'k13', 'k16'} to High School
on day 13 parent p9 carries {'k12', 'k18', 'k17', 'k14', 'k19'} to High School
on day 14 parent p1 carries {'k18', 'k3', 'k17'} to High School
on day 14 parent p10 carries {'k12', 'k19', 'k15', 'k13', 'k16', 'k14'} to High School
on day 14 parent p4 carries {'k6', 'k4', 'k11', 'k8'} to Middle School
on day 14 parent p5 carries {'k9', 'k0', 'k7', 'k2'} to Middle School
on day 14 parent p6 carries {'k3', 'k10', 'k1', 'k5'} to Middle School
[Finished in 5.1s]