Abstract
A multi-period highway maintenance scheduling program was formulated as a large scale 0-1 integer nonlinear program (INLP). A number of other real world multi-period investment problems can also be formulated in a similar manner. Relaxation, decomposition, and network formulations were used to convert the 0-1 INLP problem to an equivalent 0-1 integer linear programming (0-1 ILP) problem. The resulting 0-1 ILP problem, a large scale problem, was solved by using a heuristic technique. This solution methodology generates 'good' solutions to the 0-1 INLP problems in a reasonable amount of computational time. An algorithm and a computer program, based upon the proposed methodology, were also developed. A number of test problems were randomly generated and solved to test the computational efficiency of the proposed algorithm. Solutions to the test problems obtained from the proposed algorithm were compared against those obtained from an exact 0-1 ILP algorithm. It was found that differences in the objective function values were less than 5% for nearly all test cases, while solutions to many test problems were optimal. The proposed algorithm solved problems with approximately 5000 0-1 variables in less than 5 minutes of CPU time on an AMDAHL 470V/6 computer. Finally, a sample highway maintenance problem was solved. The capability of the algorithm to select and schedule maintenance for highways requiring periodic maintenance was demonstrated. The sample problem had 1350 0-1 variables and about 1000 constraints. This problem was solved in approximately 6 seconds of CPU time on an AMDAHL 470V/6 computer. Thus, it was concluded that the proposed algorithm is a tool for obtaining approximate (near-optimal) solutions to large scale 0-1 INLP problems in a reasonable amount of computational time.
Sathaye, Shashikant (1980). Network decomposition procedures for a time-phased highway maintenance scheduling problem. Texas A&M University. Texas A&M University. Libraries. Available electronically from
https : / /hdl .handle .net /1969 .1 /DISSERTATIONS -644619.