Difference of Convex Functions Optimization Methods: Algorithm of Minimum Maximal Network Flow Problem with Time-Windows
Keywords:
Optimization network, Minimum flow problem, Difference of convex functions optimization, Time-windows.Abstract
In this paper, we consider the minimum maximal network flow problem, i.e., minimizing the flow value, minimizing the total time among maximal flow with time-windows, which is a combinatorial optimization and an NP-hard problem. After a mathematical modeling problem, we introduce some formulations of the problem and one of them is a minimization of a concave function over a convex set. The problem can also be cast into a difference of convex functions programming (nonconvex optimization). We propose in this work a new algorithm for solving the Minimum Maximal Network Flow Problem with Time-Windows (MMNFPTW).
References
N. El-Sherbeny. (2015). "Minimum Convex and Differentiable Cost Flow Problem with Time- Windows". International Journal of Sciences: Basic and Applied Research, Vol. (20), No. (1), pp. 139-150. Available: http://gssrr.org/index.php?journal=JournalOfBasicAndApplied
N. El-Sherbeny. (2015). "The Dynamic Shortest Path Problems of Minimum Cost Length Time Windows and Time-Varying Costs". International Journal of Scientific and Innovative Mathematical Research, Vol. (3), No. (3), pp. 47-55. Available: www.arcjournal.org
N. El-Sherbeny. (2014). "The Algorithm of the Time-Dependent Shortest Path Problem with Time-Windows". Applied Mathematics, Vol. (5), No. (17), pp. 2764-2770. Available: http://dx.doi.org/10.4236/am.2014.517264
N. El-Sherbeny. (2011). "Imprecision and flexible constraints in fuzzy vehicle routing problem". American Journal of Mathematical and Management Sciences, Vol. 31, pp. 55-71. Available: http://dx.doi.org/10.1080/01966324.2011.10737800
N. El-Sherbeny. And D. Tuyttens. ''Optimization multicriteria of routing problem''. Troisieme Journee de Travail sur la Programming Mathematique Multi-Objective, Faculte Polytechnique de Mons, Mons, Belgique, (2001).
N. El-Sherbeny. ''Resolution of a vehicle routing problem with multiobjective simulated annealing method''. Ph.D., Mathematics Department, Faculty of Science, Mons University, Mons, Belgium, 2001.
R. Horst and H. Tuy. (1993). Global optimization, Deterministic Approaches. (2nd edition). Springer-Verlag.
M. Iri. "An essay in the theory of uncontrollable flows and congestion". Technical Report. Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, TRISE 94-03, 1994.
D. Pham and T. Le Thi. "Convex analysis approach to d. c. programming theory, algorithms and applications". Acta Mathematica Vietnamica, Vol. 22, pp. 289-355, 1997.
D. Pham. "Duality in d. c. (difference of convex functions) optimization. Sub-gradient methods". Trends in Mathematical Optimization, International Series of Numerical Mathematics 84, Birkhauser pp. 277-293, 1988.
J. Phillips. "Algorithms for the vector maximization problem". Mathematical Programming, Vol. 2, pp. 207-229, 1972.
J. Shi and Y. Yamamoto. "A global optimization method for minimum maximal flow problem". ACTA Mathematica Vol., 22, pp. 271-287, 1997.
M. Shigeno, I. Takahashi and Y. Yamamoto. "Minimum maximal flow problem: an optimization over the efficient set". Journal of Global Optimization, Vol. 25, pp. 425-443, 2003.
Y. Yamamoto. "Optimization over the efficient set, Overview". Journal of Global Optimization, Vol. 1-4, pp. 285-317, 2001.
D. Tuyttens, J. Teghem, N. El-Sherbeny. (2004). "A Particular Multiobjective Vehicle Routing Problem Solved by Simulated Annealing". Lecture Notes in Economics and Mathematical Systems, Vol. 535, pp. 133-152, Springer-Verlag, Berlin, Germany. Available: http://dx.doi.org/10.1007/978-3-642-17144-4
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers with this journal agree to the following terms.
