Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
AbstractWe present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where the temporal constraints, in the literature, usually are remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usability. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct usage of a commercial solver against the proposed heuristic where the latter approach can find high quality solutions within distinct time limits.
Download InfoTo our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
Bibliographic InfoPaper provided by Department of Business and Management Science, Norwegian School of Economics in its series Discussion Papers with number 2006/18.
Length: 20 pages
Date of creation: 01 Dec 2006
Date of revision:
Contact details of provider:
Postal: NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Phone: +47 55 95 92 93
Fax: +47 55 95 96 50
Web page: http://www.nhh.no/en/research-faculty/department-of-business-and-management-science.aspx
More information through EDIRC
Routing; Scheduling; Temporal Constraints; Synchronization; Branch and Bound;
Find related papers by JEL classification:
- C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Ioachim, Irina & Desrosiers, Jacques & Soumis, Francois & Belanger, Nicolas, 1999. "Fleet assignment and routing with schedule synchronization constraints," European Journal of Operational Research, Elsevier, vol. 119(1), pages 75-90, November.
- Bredström, David & Rönnqvist, Mikael, 2007. "A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints," Discussion Papers 2007/7, Department of Business and Management Science, Norwegian School of Economics.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Stein Fossen).
If references are entirely missing, you can add them using this form.