Search results

The aim of the study is to show that merging two areas of mathematics – topology and discrete optimization – could result in a viable option to solve classical or specialized integer problems.

In the paper, discrete topology concepts are applied to propose a metaheuristic algorithm that is capable to solve binary programming problems. Particularly, some of the homotopy for paths principles are used to explore the solution space associated with four well-known NP-hard problems herein considered as follows: knapsack, set covering, bi-level single plant location with order and one-max.

Computational experimentation confirms that the proposed algorithm performs in an effective manner, and it is able to efficiently solve the sets of instances used for the benchmark. Moreover, the performance of the proposed algorithm is compared with a standard genetic algorithm (GA), a scatter search (SS) method and a memetic algorithm (MA). Acceptable results are obtained for all four implemented metaheuristics, but the path homotopy algorithm stands out.

A novel metaheuristic is proposed for the first time. It uses topology concepts to design an algorithmic framework to solve binary programming problems in an effective and efficient manner.

One of the most important problems concerning the toll roads is the setting of an appropriate cost for traveling through private arcs of a transportation network. The purpose of this paper is to consider this problem by stating it as a bilevel programming (BLP) model. At the upper level, one has a public regulator or a private company that manages the toll roads seeking to increase its profits. At the lower level, several companies-users try to satisfy the existing demand for transportation of goods and/or passengers, and simultaneously, to select the routes so as to minimize their travel costs. In other words, what is sought is kind of a balance of costs that bring the highest profit to the regulating company (the upper level) and are still attractive enough to the users (the lower level).

With the aim of providing a solution to the BLP problem in question, a direct algorithm based on sensitivity analysis (SA) is proposed. In order to make it easier to move (if necessary) from a local maximum of the upper level objective function to another, the well-known “filled function (FF)” method is used.

The paper proposes and tests two versions of the heuristic algorithm to solve the toll optimization problem (TOP) based upon SA for linear programming (LP) problems. The algorithm makes use of an SA procedure for the LP problem at the lower level, as well as of the “filled” function technicalities in order to reach the global optimum when “jammed” at some local optimum. Numerical experiments with a series of small and medium dimension test problems show the proposed algorithm’s robustness and decent convergence characteristics.

Numerical experiments with a series of small- and medium dimension test problems show the proposed algorithm’s robustness and reasonable convergence characteristics. In particular, while ceding in efficiency to other algorithms when solving small problems, the proposed method wins in the case of medium (higher dimensional) test models. Because of that, one can expect a serious real-life impact on the TOP when the proposed methods and/or their improved versions are developed further to be applicable in practice in the near future.

The proposed algorithms are original and perform well when solving small and medium test numerical problems. The proposed heuristics aim at filling in a gap in a series of numerical approaches to the solution of TOP problem listed in the Introduction. To the authors knowledge, no systematic attempts to apply the SA tools to the toll assigned problem have been recently made. Moreover, the combination of these powerful tools with the “FFs” techniques brings forward some new global optimization ideas. Exactly these features build up the knowledge this specific paper offers in relation to previous relevant works.