| Article ID: | iaor19981394 |
| Country: | United Kingdom |
| Volume: | 33 |
| Issue: | 12 |
| Start Page Number: | 1 |
| End Page Number: | 13 |
| Publication Date: | Jun 1997 |
| Journal: | Computers & Mathematics with Applications |
| Authors: | Ruland K.S., Rodin E.Y. |
| Keywords: | programming: travelling salesman, vehicle routing & scheduling |
This paper formulates the pickup and delivery problem, also known as the dial-a-ride problem, as an integer program. Its polyhedral structure is explored and four classes of valid inequalities are developed. The results of a branch-and-cut algorithm based on these constraints are presented.