Approximation algorithms for route planning with nonlinear objectives
Abstract
We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs to capture a penalty for early arrival. It is known that as nonlinearity arises, the problem becomes NP-hard and little is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efficiently computed under some natural constraints. In particular, we provide a fully polynomial approximation scheme under hop constraints. Our approximation algorithm can extend to run in pseudo-polynomial time under a more general linear constraint that sometimes is useful. As a by-product, we show that our algorithm can be applied to the problem of finding a path that is most likely to be on time for a given deadline.
References
[1]
Ahuja, R.; Batra, J.; and Gupta, S. 1983. Combinatorial optimization with rational objective functions: A communication. Mathematics of Operations Research 8(2):314-314.
[2]
Bar-Gera, H. 2002. Transportation network test problems.
[3]
Correa, J.; Fernandes, C. G.; and Wakabayashi, Y. 2010. Approximating a class of combinatorial problems with rational objective function. Mathematical programming 124(1-2):255-269.
[4]
Goyal, V., and Ravi, R. 2013. An fptas for minimizing a class of low-rank quasi-concave functions over a convex set. Operations Research Letters 41(2):191-196.
[5]
Guérin, R. A., and Orda, A. 1999. Qos routing in networks with inaccurate information: theory and algorithms. IEEE/ACM Transactions on Networking (TON) 7(3):350-364.
[6]
Horst, R.; Pardalos, P. M.; and Van Thoai, N. 2000. Introduction to global optimization. Springer Science & Business Media.
[7]
Karger, D.; Motwani, R.; and Ramkumar, G. 1997. On approximating the longest path in a graph. Algorithmica 18(1):82-98.
[8]
Kelner, J. A., and Nikolova, E. 2007. On the hardness and smoothed complexity of quasi-concave minimization. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, 472-482. IEEE.
[9]
Megiddo, N. 1979. Combinatorial optimization with rational objective functions. Mathematics of Operations Research 4(4):414-424.
[10]
Mittal, S., and Schulz, A. S. 2013. An fptas for optimizing a class of low-rank functions over a polytope. Mathematical Programming 141(1-2):103-120.
[11]
Nikolova, E.; Kelner, J. A.; Brand, M.; and Mitzenmacher, M. 2006. Stochastic shortest paths via quasi-convex maximization. In Algorithms–ESA 2006, 552-563. Springer.
[12]
Nikolova, E.; Brand, M.; and Karger, D. R. 2006. Optimal route planning under uncertainty. In ICAPS, volume 6, 131-141.
[13]
Nikolova, E. 2010. Approximation algorithms for offline risk-averse combinatorial optimization.
[14]
Papadimitriou, C. H., and Yannakakis, M. 2000. On the approximability of trade-offs and optimal access of web sources. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, 86-92. IEEE.
[15]
Tsaggouris, G., and Zaroliagis, C. 2009. Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications. Theory of Computing Systems 45(1):162-186.
[16]
Yang, G., and Nikolova, E. 2015. Approximation algorithms for route planning with nonlinear objectives. arXiv preprint arXiv:1511.07412.
- Approximation algorithms for route planning with nonlinear objectives
Recommendations
Path Planning with Objectives Minimum Length and Maximum Clearance
Topics in Theoretical Computer ScienceAbstractIn this paper, we study the problem of bi-objective path planning with the objectives minimizing the length and maximizing the clearance of the path, that is, maximizing the minimum distance between the path and the obstacles. The goal is to find ...
Three Objectives Degrade the Convergence Ability of Dominance-Based Multi-objective Evolutionary Algorithms
Parallel Problem Solving from Nature – PPSN XVIIIAbstractIn the evolutionary multi-objective optimization (EMO) community, it is well known that the convergence ability of dominance-based multi-objective evolutionary algorithms (MOEAs) is severely deteriorated on many-objective problems with more than ...
Handling multiple objectives with biogeography-based optimization
Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2016
4406 pages
Sponsors
- Association for the Advancement of Artificial Intelligence
Publisher
AAAI Press
Publication History
Published: 12 February 2016
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 04 Jan 2025