Sharif Digital Repository

We revisit the problem of finding (Formula presented.) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the (Formula presented.) paths. We provide a (Formula presented.)-approximation algorithm for this problem, improving the best previous approximation factor of (Formula presented.). We also provide the first approximation algorithm for the problem with a sublinear approximation factor of (Formula presented.), where (Formula presented.) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be... 

Equity in distribution is one of the most controversial and essential concepts which for a long time has been the central concern of political philosophers when considering planning concerns of the societies. Transport is a key field by which politicians and decision-makers impose their intention on societies. Although there have been studies discussing equity in transport, yet there is no clear mathematical framework to utilize the equity concept in transportation planning. This study has reviewed equity in transportation, as well as in human science studies to investigate and determine how transportation advantages should be equitably distributed among society members. This review has led... 

The problem of Rapid Transit Network Design (RTND) is studied in this paper. Due to the noticeable contribution of rapid transit lines in public transportation network of large urban areas, this problem is interesting to the transportation specialists. On the other hand, the success stories of Bus Rapid Transit (BRT) systems in different countries have motivated us to study BRT network planning. BRT systems can be developed with less investment costs and construction time in comparison with rail-based systems. Therefore, planning Bus Rapid Transit lines, either to develop a new rapid transit network or extend a current one can be an interesting research topic. This problem, like other... 

Transportation network design problem (TNDP) aims to choose from among a set of alternatives (e.g., set of new arcs) which minimizes an objective (e.g., total travel time), while keeping consumption of resources (e.g., budget) within their limits. TNDP is formulated as a bilevel programming problem, which is difficult to solve on account of its combinatorial nature. Following a recent, heuristic by ant colony optimization (ACO), a hybridized ACO (HACO) has been devised and tested on the network of Sioux Falls, showing that the hybrid is more effective to solve the problem. In this paper, employing the heuristic of particle swarm optimization (PSO), an algorithm is designed to solve the TNDP.... 

Medical waste management (MWM) is an important and necessary problem in the COVID-19 situation for treatment staff. When the number of infectious patients grows up, the amount of MWMs increases day by day. We present medical waste chain network design (MWCND) that contains health center (HC), waste segregation (WS), waste purchase contractor (WPC), and landfill. We propose to locate WS to decrease waste and recover them and send them to the WPC. Recovering medical waste like metal and plastic can help the environment and return to the production cycle. Therefore, we proposed a novel viable MWCND by a novel two-stage robust stochastic programming that considers resiliency (flexibility and... 

Decentralized supply chain management is found to be significantly relevant in today’s competitive markets. Production and distribution planning is posed as an important optimization problem in supply chain networks. Here, we propose a multi-period decentralized supply chain network model with uncertainty. The imprecision related to uncertain parameters like demand and price of the final product is appropriated with stochastic and fuzzy numbers. We provide mathematical formulation of the problem as a bi-level mixed integer linear programming model. Due to problem’s convolution, a structure to solve is developed that incorporates a novel heuristic algorithm based on Kth-best algorithm, fuzzy... 

Decentralized supply chain management is found to be significantly relevant in today’s competitive markets. Production and distribution planning is posed as an important optimization problem in supply chain networks. Here, we propose a multi-period decentralized supply chain network model with uncertainty. The imprecision related to uncertain parameters like demand and price of the final product is appropriated with stochastic and fuzzy numbers. We provide mathematical formulation of the problem as a bi-level mixed integer linear programming model. Due to problem’s convolution, a structure to solve is developed that incorporates a novel heuristic algorithm based on Kth-best algorithm, fuzzy... 

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(p ) on the price of anarchy, i.e., the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for = O(pn) and for ≥ 12 n [dlg] n, and that the price of anarchy is 15 1 + (min{α 2/n , n2 })1/3 for any . The latter bound shows the first... 

Given a graph G with a set of terminals, two weight functions c and d defined on the edge set of G, and a bound D, a popular NP-hard problem in designing networks is to find the minimum cost Steiner tree (under function c) in G, to connect all terminals in such a way that its diameter (under function d) is bounded by D. Marathe et al. (J. Algoritm. 28(1), 142–171, 1998) proposed an (O(lnn),O(lnn)) approximation algorithm for this bicriteria problem, where n is the number of terminals. The first factor reflects the approximation ratio on the diameter bound D, and the second factor indicates the cost-approximation ratio. Later, Kapoor and Sarwat (Theory Comput. Syst. 41(4), 779–794, 2007)... 

High reliability, low power consumption and high performance are key objectives in the design of NoCs. These three design objectives should be considered simultaneously in order to have an optimal design. This paper proposes a method to reduce power consumption of an application specific NoC. This is done in two steps: 1) Extra virtual channels are used in the router architecture to increase the performance in an application specific NoC, and 2) The amount of the performance gain is then set to the initial point using frequency scaling technique, hence reducing the power consumption, without corruption of reliability. The simulation results show that the method can reduce the power... 

Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense... 

Supply chain management integrates planning and controlling of materials, information, and finances in a process which begins from suppliers and ends with customers. Optimal planning decisions made in such a distribution network usually include transportation, facilities location, and inventory. This study presents a new approach for considering customers’ differentiation in an integrated location-allocation and inventory control model using transfer recurrent neural network (RNN). In this study, a location and allocation problem is integrated with inventory control decisions considering two classes of strategic and non-strategic customers. For the first time, a novel transfer RNN is applied...