Abstract
We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. Barnhart, N. Boland, L. Clarke, E.L. Johnson, G.L. Nemhauser and R.G. Shenoi, Flight string models for aircraft fleeting and routing, Transportation Science 32 (1998) 208–220.
S.E. Butt and D.M. Ryan, An optimal solution procedure for the multiple tour maximum collection problem using column generation, Computers and Operations Research 26 (1999) 427–441.
Y. Crama and A.G. Oerlemans, A column generation approach to job grouping for flexible manufacturing systems, European Journal of Operational Research 78 (1994) 58–80.
G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8 (1960) 101–111.
P.R. Day and D.M. Ryan, Flight attendant rostering for short-haul airline operations, Operations Research 45 (1997) 649–661.
G. Desaulniers, J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon and F. Soumis, Crew pairing at Air France, European Journal of Operational Research 97 (1997) 245–259.
M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research 40 (1992) 342–354.
M. Desrochers and F. Soumis, A column generation approach to the urban transit crew scheduling problem, Transportation Science 23 (1989) 1–13.
Y. Fathi, S.R. Kegler and C.T. Culbreth, A column generation procedure for gang-rip saw arbor design and scheduling, International Journal of Production Research 34 (1996) 313–327.
R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Languarge for Mathematical Programming (Boyd and Fraser, 1993).
P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem, Operations Research 9 (1961) 849–859.
P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem: Part II, Operations Research 11 (1961) 863–888.
Ilog Inc., Ilog Cplex 6.5 Reference Manual.
N. Kohl and O.B.G. Madsen, An optimization algorithm for the vehicle routing problem with time windows based on Lagrangean relaxation, Operations Research 45 (1997) 395–406.
S. Lavoie, M. Minoux and E. Odier, A new approach for crew pairing problems by column generation with an application to air transportation, European Journal of Operational Research 35 (1988) 45–58.
G.L. Nemhauser, M.W.P. Savelsbergh and G.S. Sigismondi, MINTO, a Mixed INTeger Optimizer, Operations Research Letters 15 (1994) 47–58.
G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization (Wiley, 1988).
F. Soumis, Decomposition and column generation, GERAD Research Report G-97-42 (1997).
J.M. Valério de Carvalho and A.J. Guimaraes Rodrigues, An LP-based approach to a two-stage cutting stock problem, European Journal of Operational Research 84 (1995) 580–589.
P.H. Vance, C. Barnhart, E.L. Johnson and G.L. Nemhauser, Solving binary cutting stock problems by column generation and branch-and-bound, Computational Optimization and Applications 3 (1994) 111–130.
P.H. Vance, Branch-and-price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications 9 (1998) 211–228.
M. van den Akker, LP-based solution methods for single-machine scheduling problems, Ph.D. Thesis, Technische Universiteit Eindhoven (1994).
F. Vanderbeck, Computational study of a column generation algorithm for bin packing and cutting stock problems, University of Cambridge, Research Papers in Management Studies 14 (1996).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Boland, N., Surendonk, T. A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints. Annals of Operations Research 108, 143–156 (2001). https://doi.org/10.1023/A:1016059012379
Issue Date:
DOI: https://doi.org/10.1023/A:1016059012379