Applied idea for the Calculation Method of Pareto Solutions of a Two-Objective Network  

Oleh:

Akiba, Tomoaki ; Takahashi, Natsumi ; Nomura, Shuhei ; Yamamoto, Hisashi

Jenis: Article from Proceeding
Dalam koleksi: The 14th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS), 3-6 December 2013 Cebu, Philippines, page 1-9.
Topik: Two-objective network; Shortest path problem; Pareto solutions; Extended Dijkstra's algorithm
Fulltext: 1092.pdf (577.39KB)

Isi artikel

The shortest path problem is a kind of optimization problems and its aim is to find the shortest path connecting two specific nodes in a network, where each edges has its distance. When considering not only the distances between the nodes but also some other information, the problem is formulated as a multi-objective shortest path problem that involves multiple conflicting objective functions. The multi-objective shortest path problem is a kind of optimization problem of multi-objective network. The multi-objective network model can be applied to common problems with many conditions, for example, optimal routing of a network connection to the Internet services, optimally scheduling of a production and distribution systems, and multistage-structured model for supply chain management systems, etc. In the general cases, multi-objectives are rarely optimized by a solution because multi-objective shortest path problem is a kind of multi-objective optimization problem. So, to solve the multi-objective shortest path problem needs to obtain Pareto solutions. An algorithm for this problem has been proposed by using extended Dijkstra's algorithm. However, this algorithm for obtaining Pareto solutions does non-useful searches. In this study, we consider two-objective shortest path problem and propose efficient algorithms with applied ideas for obtaining the Pareto solutions. Our proposed algorithm can reduce more search space than existing algorithm, by solving a single-objective shortest path problem. The results of the numerical experiments suggest that our proposed algorithms reduce the computing time and the memory size for obtaining the Pareto solutions.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali