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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/4779 |
| Date | 25 April 2007 |
| Creators | Chen, Ping-Shun |
| Contributors | Garcia-Diaz, Alberto |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | 396955 bytes, electronic, application/pdf, born digital |
Page generated in 0.0021 seconds