Patent Document ID: 7978629
Application ID: 12380064
Patent Flag: 1

Claim One:
1. A method for installing a conveyance linking a service provider location with customer locations selected from potential customer locations located on potential conveyance routes, the installed conveyance comprising a network yielding a total profit within a predetermined bound of a maximum possible total revenue, each potential customer location being associated with a potential customer revenue and each potential conveyance route being associated with a potential cost of the conveyance, the method comprising: formulating an optimization problem for the network as a prize-collecting Steiner tree problem in graphs (PCSPG) with potential conveyance routes x e between locations of potential customers as edges and locations of potential customers y i as vertices, the PCSPG including a plurality of network generalized subtour elimination constraint (GSEC) inequalities; replacing each y i with a complement z i =1−y i ; dualizing a subset of the GSEC inequalities in a Lagrangian fashion; in a computer processor, performing the following in a subgradient method (SM) iteration k on a solution ( x k , z k ) to determine a near-optimal or optimal solution to the PCSPG: obtaining a lower bound w λ k to the PCSPG by performing Lagrangian relaxation on a vector of multipliers λ corresponding to the GSEC inequalities; terminating the iteration if ( w −w λ k )<1, where w is a previously obtained valid upper bound, the current ( x k , z k ) being determined to be the network solution; performing a Lagrangian heuristic including a Minkoff algorithm on a solution ( x k , z k ) using complementary costs and penalties as input and using no root vertex as input, the heuristic further including a pruning algorithm using original costs and penalties as input, the heuristic producing an upper bound replacing w if the upper bound is lower than w ; applying a linear programming-based reduced cost test defined by the solution ( x k , z k ) to identify edges that are not in any optimal solution, and eliminating those edges from further consideration; dualizing those GSECs not yet dualized that violate the solution ( x k , z k ), those GSECs having a cardinality greater than 2; and updating the Lagrangian multipliers λ; if the iteration has not been terminated and if an iteration limitation criterion has not been reached, then initiating a new iteration; if the iteration has been terminated, or if the iteration limitation criterion has been reached, then outputting an optimal or near-optimal solution to the PCSPG; and installing the conveyance along selected potential conveyance routes according to the output solution.