A Partial Duty Formulation for Crew Scheduling
We consider a crew scheduling problem with a break, working time, and duty length constraint. It is common to solve crew scheduling problems with a diving heuristic, using column generation to solve the LP relaxation of a set partitioning formulation where variables correspond with duties. We prove that computing the LP bound of this formulation is weakly NP-hard, and propose an alternative formulation based on partial duties, whose LP bound can be computed in polynomial time. We prove the same complexity results for the corresponding pricing problems. However, the partial duty formulation…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.24867
curl -X POST /api/v1/records/arxiv/2610.24867/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.24867/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'