Cost minimization in multi−commodity multi−mode generalized networks with time windows
Loading...
Date
2007-04-25
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Texas A&M University
Abstract
The purpose of this research is to develop a heuristic algorithm to minimize total
costs in multi-commodity, multi-mode generalized networks with time windows
problems. The proposed mathematical model incorporates features of the congestion of
vehicle flows and time restriction of delivering commodities. The heuristic algorithm,
HA, has two phases. Phase 1 provides lower and upper bounds based on Lagrangian
relaxations with subgradient methods. Phase 2 applies two methods, early due date with
overdue-date costs and total transportation costs, to search for an improved upper bound.
Two application networks are used to test HA for small and medium-scale
problems. A different number of commodities and various lengths of planning time
periods are generated. Results show that HA can provide good feasible solutions within
the reasonable range of optimal solutions. If optimal solutions are unknown, the average
gap between lower and upper bounds is 0.0239. Minimal and maximal gaps are 0.0007
and 0.3330. If optimal solutions are known, the maximal gap between upper bounds and
optimal solutions is less than 10% ranges of optimal solutions.
Description
Keywords
Lagrangian relaxation, Multi-commodity, Multi-mode, Generalized network, Time windows