Minimum work paths in elevated networks
A new variant of the shortest path problem involves a bicycle traveling from an origin to a destination through a network situated on a hilly geography. Determining a path that takes the least amount of pedaling work involves a conservative force, gravity, and a nonconservative force, friction, acting on the bicycle. The cyclist's pedaling work to overcome the friction of each arc varies with the bicycle's kinetic and gravitational potential energies, which transform to one another. Although geometric characteristics of the network are invariable, arc weights representing required pedaling work are variable. This problem is formulated as a quadratic integer program and an approximation procedure is presented. (C) 2008 Wiley Periodicals, Inc.
networks shortest paths physical constraints state-dependent dynamic programming