Cost-time trade-off Königsberg bridge problem traversing all the seven bridges allowing repetition

An extended version of Königsberg bridge problem is considered. After having split into two streams, Pregel River flows through the city of Königsberg, now known as Kaliningrad, forming two islands. Seven bridges are built across the river providing links among the four land masses consisting of two islands, right and left banks of the river. Costs and times of traversing the bridges are given. The set of nondominated solutions of this problem is obtained providing the total cost and total time of nondominated paths starting from one land mass and returning to it after having traversed all the seven bridges allowing repetition. The problem is solved in two phases. In the first phase, the problem is represented by a graph whose nodes represent the land masses and edges represent the bridges. In the second phase, the set of nondominated solutions of the problem is obtained through generating and solving a sequence of prioritized bicriterion problems, all of whose nodes are of even degree. The generation of the sequence of prioritized bicriterion problems is done through augmenting the number of edges by duplicating some edges in the graph representing the problem in such a way that all the nodes in each of the prioritized bicriterion problems are of even degree; earlier all the nodes in the graph representing the problem were of odd degree. Now, since, each of the prioritized bicriterion problems has all the nodes of even degree, each of them is amenable to solution by Cycle finding and Fleury’s algorithms.