This paper describes a bi-level programming model that seeks to simultaneously optimize location and design decisions of facilities in a distribution system in order to realize company's maximal total profit subje...This paper describes a bi-level programming model that seeks to simultaneously optimize location and design decisions of facilities in a distribution system in order to realize company's maximal total profit subject to the constraints on the facility capacity and the investment budget.In the upper-level problem,twoechelon integrated competitive/uncompetitive capacitated facility location model,which involves facility location and design,is presented.In the lower-level problem,customer is assumed to patronize store based on facility utility which is expressed by service time cost in the store and its travel cost to customer.Customer's facility choice behavior is presented by a stochastic user equilibrium assignment model with elastic demand.Since such a distribution system design problem belongs to a class of NP-hard problem,a genetic algorithm(GA)-based heuristic procedure is presented.Finally,a numerical example is used to illustrate the application of the proposed model and some parameter sensitivity analyses are presented.展开更多
The present study developed and tested a method to evaluate the location of aged care facilities from the viewpoint of whether they are equitably located for users,using the improved Median Share Ratio(MSR).By evaluat...The present study developed and tested a method to evaluate the location of aged care facilities from the viewpoint of whether they are equitably located for users,using the improved Median Share Ratio(MSR).By evaluating the current location of aged care facilities,it is possible to extract the districts which are short of facilities.The evaluation method was applied to Chofu and Kiyose Cities in Tokyo Metropolis,Japan,and the evaluation result of weighting and that of not weighting by elderly population were compared and discussed.Consequently,adopting the evaluation method with weighting by elderly population,it is possible to adequately examine the districts where new aged care facilities should be constructed.From this evidence,it is significant to evaluate the location of aged care facilities,using the improved MSR with weighting by elderly population in the study.展开更多
First a remanufactming logistics network is con- structed, in which the structure of both the forward logistics and the reverse logistics are of two levels and all the logistics facilities are capacitated. Both the re...First a remanufactming logistics network is con- structed, in which the structure of both the forward logistics and the reverse logistics are of two levels and all the logistics facilities are capacitated. Both the remanufactming products and the new products can be used to meet the demands of customers. Moreover, it is assumed that homogeneous facilities can be designed together into integrated ones, based on which a mixed integer nonlinear programming （MINLP） facility location model of the remanufacturing logistics network with six types of facilities to be sited is built. Then an algorithm based on enumeration for the model is given. The feasible combinations of binary variables are searched by enumeration, and the remaining sub-problems are solved by the LP solver. Finally, the validities of the model and the algorithm are illustrated by means of an example. The result of the sensitivity analysis of parameters indicates that the integration of homogeneous facilities may influence the optimal solution of the problem to a certain degree.展开更多
To smooth the correlation process from bio-virus diffusion to emergency relief response,the Gaussian plume model is used to describe the diffusion of dangerous sources,where the bio-virus concentration at any given po...To smooth the correlation process from bio-virus diffusion to emergency relief response,the Gaussian plume model is used to describe the diffusion of dangerous sources,where the bio-virus concentration at any given point in affected areas can be calculated.And the toxic load rule is introduced to define the borderline of the dangerous area at different levels.Combined with this,different emergency levels of different demand points in dangerous areas are confirmed using fuzzy clustering,which allows demand points at the same emergency level to cluster in a group.Some effective emergency relief centers are chosen from the candidate hospitals which are located in different emergency level affected areas by set covering.Bioterrorism experiments which were conducted in Nanjing,Jiangsu province are simulated,and the results indicate that the novel method can be used efficiently by decision makers during an actual anti-bioterrorism relief.展开更多
develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining...develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining with the greedy aug- previous ratio 3 to 1.8526.展开更多
Determining the optimum location of facilities is critical in many fields,particularly in healthcare.This study proposes the application of a suitable location model for field hospitals during the novel coronavirus 20...Determining the optimum location of facilities is critical in many fields,particularly in healthcare.This study proposes the application of a suitable location model for field hospitals during the novel coronavirus 2019(COVID-19)pandemic.The used model is the most appropriate among the three most common location models utilized to solve healthcare problems(the set covering model,the maximal covering model,and the P-median model).The proposed nonlinear binary constrained model is a slight modification of the maximal covering model with a set of nonlinear constraints.The model is used to determine the optimum location of field hospitals for COVID-19 risk reduction.The designed mathematical model and the solution method are used to deploy field hospitals in eight governorates in Upper Egypt.In this case study,a discrete binary gaining–sharing knowledge-based optimization(DBGSK)algorithm is proposed.The DBGSK algorithm is based on how humans acquire and share knowledge throughout their life.The DBGSK algorithm mainly depends on two junior and senior binary stages.These two stages enable DBGSK to explore and exploit the search space efficiently and effectively,and thus it can solve problems in binary space.展开更多
Facility location problem is a kind of NP-Hard combinational problem.Considering ever-changing demand sites,demand quantity and releasing cost,we formulate a model combining tabu search and FCM(fuzzy clustering method...Facility location problem is a kind of NP-Hard combinational problem.Considering ever-changing demand sites,demand quantity and releasing cost,we formulate a model combining tabu search and FCM(fuzzy clustering method) to solve the capacitated dynamic facility location problem.Some results are achieved and they show that the proposed method is effective.展开更多
The differential evolution algorithm is an evolutionary algorithm for global optimization and the un-capacitated facility location problem (UFL) is one of the classic NP-Hard problems. In this paper, combined with the...The differential evolution algorithm is an evolutionary algorithm for global optimization and the un-capacitated facility location problem (UFL) is one of the classic NP-Hard problems. In this paper, combined with the specific characteristics of the UFL problem, we introduce the activation function to the algorithm for solving UFL problem and name it improved adaptive differential evolution algorithm (IADEA). Next, to improve the efficiency of the algorithm and to alleviate the problem of being stuck in a local optimum, an adaptive operator was added. To test the improvement of our algorithm, we compare the IADEA with the basic differential evolution algorithm by solving typical instances of UFL problem respectively. Moreover, to compare with other heuristic algorithm, we use the hybrid ant colony algorithm to solve the same instances. The computational results show that IADEA improves the performance of the basic DE and it outperforms the hybrid ant colony algorithm.展开更多
A novel location-queuing problem for blood collection facilities against MPHEs is studied in this paper.The decision variables to be determined include the opening plan of fixed blood collection rooms,the location of ...A novel location-queuing problem for blood collection facilities against MPHEs is studied in this paper.The decision variables to be determined include the opening plan of fixed blood collection rooms,the location of mobile blood collecting vehicles,and the number of service desks within facilities.This problem is formulated as a bi-objective multi-period integer nonlinear programming model,incorporating unique features that distinguish it from previous studies,such as pandemic risk,blood donation behavior,and the heterogeneity of blood collection facilities.The objectives are to minimize the total system cost and maximize donor satisfaction.To solve this problem,an improved multi-objective grey wolf optimization(IMOGWO)algorithm,which incorporates chaotic mapping and adaptive convergence factors,is proposed.Real data from Chongqing,China,is utilized to demonstrate the applicability of the model and the effectiveness of IMOGWO.Using evaluation metrics such as the C metric(CM),number of Pareto frontier(NPF),maximum spread(MS),spacing(SP),mean ideal distance(MID)and computation time(CPU time),numerical experiments demonstrate that the proposed IMOGWO outperforms non-dominated sorting genetic algorithm-Ⅱ(NSGA-Ⅱ),multi-objective particle swarm optimization(MOPSO),multi-objective whale optimization(MOWOA),multi-objective chimp optimization(MOCh OA),and multi-objective grey wolf optimization(MOGWO).展开更多
Growing concerns about environmental quality of cities are calling for sustainable road transportation technologies. EV （electric vehicles）, for public and private transport, can contribute significantly to the lowe...Growing concerns about environmental quality of cities are calling for sustainable road transportation technologies. EV （electric vehicles）, for public and private transport, can contribute significantly to the lowering of the current pollution levels. However, the EV use is currently facing several weaknesses among which are： limited driving range, high cost and overall limited efficiency. Electric vehicles management is a relatively recent problem; its purpose is to expedite the establishment of a costumer convenient, cost-effective, EV infrastructure. Inspire the relevance of the problem, a few small research communities in this field work on some of its aspects. In this work, some important issues of this problem are discussed and the contribution of combinatorial optimization tools for solving some challenging subproblems is studied.展开更多
Layout design problem is to determine a suitable arrangement for the departments so that the total costs associated with the flow among departments become least. Single Row Facility Layout Problem, SRFLP, is one of &l...Layout design problem is to determine a suitable arrangement for the departments so that the total costs associated with the flow among departments become least. Single Row Facility Layout Problem, SRFLP, is one of </span></span><span style="font-family:Verdana;"><span style="font-family:Verdana;"><span style="font-family:Verdana;">the </span></span></span><span><span><span style="font-family:""><span style="font-family:Verdana;">layout problems that have many practical applications. This problem and its specific scenarios are often used to model many of the raised issues in the field of facility location. SRFLP is an arrangement of </span><i><span style="font-family:Verdana;">n</span></i><span style="font-family:Verdana;"> departments with a specified length in a straight line so that the sum of the weighted distances between the pairs of departments is minimized. This problem is NP-hard. In this paper, first, a lower bound for a special case of SRFLP is presented. Then, a general </span><span style="font-family:Verdana;">case of SRFLP is presented in which some new and real assumptions are added to generate more practical model. Then a lower bound, as well as an algorithm, is proposed for solving the model. Experimental results on some instances in literature show the efficiency of our algorithm.展开更多
The purpose of this review is to summarise the existing literature on the operational systems as to explain the current state of understanding on the coupled operational systems.The review only considers the linear op...The purpose of this review is to summarise the existing literature on the operational systems as to explain the current state of understanding on the coupled operational systems.The review only considers the linear optimisation of the operational systems.Traditionally,the operational systems are classified as decoupled,tightly coupled,and loosely coupled.Lately,the coupled operational systems were classified as systems of time-sensitive and time-insensitive operational cycle,systems employing one mix and different mixes of factors of production,and systems of single-linear,single-linear-fractional,and multi-linear objective.These new classifications extend the knowledge about the linear optimisation of the coupled operational systems and reveal new objective-improving models and new state-of-the-art methodologies never discussed before.Business areas affected by these extensions include product assembly lines,cooperative farming,gas/oil reservoir development,maintenance service throughout multiple facilities,construction via different locations,flights traffic control in aviation,game reserves,and tramp shipping in maritime cargo transport.展开更多
In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be open...In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened.There are k different kinds of products to be supplied by a set of open facilities.Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply.Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected.There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected.These service costs are assumed to be symmetric and satisfy the triangle inequality.The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities,servicing the clients,and the penalty is minimized.We address two different integer programs to describe the problem.Based on the linear programming rounding technique,we propose a(2k+1)-approximation algorithm for this problem.展开更多
Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have...Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have a potential facilities set and a clients set.Each facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be met.The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible.The CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants.Following this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty costs.As a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.展开更多
Emergency response activity relies on transportation networks. Emergency facility location interacts with transportation networks clearly. This review is aimed to provide a combined framework for emergency facility lo...Emergency response activity relies on transportation networks. Emergency facility location interacts with transportation networks clearly. This review is aimed to provide a combined framework for emergency facility location in transportation networks. The article reveals emergency response activities research clusters, issues, and objectives according to keywords co-occurrence analysis. Four classes of spatial separation models in transportation networks, including distance, routing, accessibility, and travel time are introduced. The stochastic and time-dependent characteristics of travel time are described. Travel time estimation and prediction method, travel time under emergency vehicle preemption,transportation network equilibrium method, and travel time in degradable networks are demonstrated. The emergency facilities location models interact with transportation networks, involving location-routing model, location models embedded with accessibility,location models embedded with travel time, and location models employing mathematical program with equilibrium constraints are reviewed. We then point out the-state-of-art challenges: ilities-oriented, evolution landscape and sequential decision modelling, datadriven optimization approach, and machine learning-based algorithms.展开更多
In this paper,we consider the metric uncapacitated facility location game with service installation costs.Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installa...In this paper,we consider the metric uncapacitated facility location game with service installation costs.Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.展开更多
This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned ...This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty. The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.展开更多
We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that...We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.展开更多
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened ...Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.展开更多
In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kin...In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kinds of facilities located in k levels of hierarchy.The total cost including the facility cost,connection cost and penalty cost will be jointly paid by all the clients.In the corresponding game of the k-level facility location problem with penalties,called the k-level facility location game with penalties,the total cost should be allocated to different clients.This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic,competitive,and the approximate cost recovery is 6.展开更多
基金the 2009 Science Foundation for Youths of the Department of Education of Jiangxi Province (No.GJJ09558)the 2009 Humanities and Social Science found of College of Jiangxi Province (No.GL0911)
文摘This paper describes a bi-level programming model that seeks to simultaneously optimize location and design decisions of facilities in a distribution system in order to realize company's maximal total profit subject to the constraints on the facility capacity and the investment budget.In the upper-level problem,twoechelon integrated competitive/uncompetitive capacitated facility location model,which involves facility location and design,is presented.In the lower-level problem,customer is assumed to patronize store based on facility utility which is expressed by service time cost in the store and its travel cost to customer.Customer's facility choice behavior is presented by a stochastic user equilibrium assignment model with elastic demand.Since such a distribution system design problem belongs to a class of NP-hard problem,a genetic algorithm(GA)-based heuristic procedure is presented.Finally,a numerical example is used to illustrate the application of the proposed model and some parameter sensitivity analyses are presented.
文摘The present study developed and tested a method to evaluate the location of aged care facilities from the viewpoint of whether they are equitably located for users,using the improved Median Share Ratio(MSR).By evaluating the current location of aged care facilities,it is possible to extract the districts which are short of facilities.The evaluation method was applied to Chofu and Kiyose Cities in Tokyo Metropolis,Japan,and the evaluation result of weighting and that of not weighting by elderly population were compared and discussed.Consequently,adopting the evaluation method with weighting by elderly population,it is possible to adequately examine the districts where new aged care facilities should be constructed.From this evidence,it is significant to evaluate the location of aged care facilities,using the improved MSR with weighting by elderly population in the study.
基金The National Natural Science Foundation of China(No.70472033).
文摘First a remanufactming logistics network is con- structed, in which the structure of both the forward logistics and the reverse logistics are of two levels and all the logistics facilities are capacitated. Both the remanufactming products and the new products can be used to meet the demands of customers. Moreover, it is assumed that homogeneous facilities can be designed together into integrated ones, based on which a mixed integer nonlinear programming （MINLP） facility location model of the remanufacturing logistics network with six types of facilities to be sited is built. Then an algorithm based on enumeration for the model is given. The feasible combinations of binary variables are searched by enumeration, and the remaining sub-problems are solved by the LP solver. Finally, the validities of the model and the algorithm are illustrated by means of an example. The result of the sensitivity analysis of parameters indicates that the integration of homogeneous facilities may influence the optimal solution of the problem to a certain degree.
基金The National Natural Science Foundation of China(No.70671021)the National Key Technology R&D Program of China during the 11th Five-Year Plan Period(No.2006BAH02A06)
文摘To smooth the correlation process from bio-virus diffusion to emergency relief response,the Gaussian plume model is used to describe the diffusion of dangerous sources,where the bio-virus concentration at any given point in affected areas can be calculated.And the toxic load rule is introduced to define the borderline of the dangerous area at different levels.Combined with this,different emergency levels of different demand points in dangerous areas are confirmed using fuzzy clustering,which allows demand points at the same emergency level to cluster in a group.Some effective emergency relief centers are chosen from the candidate hospitals which are located in different emergency level affected areas by set covering.Bioterrorism experiments which were conducted in Nanjing,Jiangsu province are simulated,and the results indicate that the novel method can be used efficiently by decision makers during an actual anti-bioterrorism relief.
基金supported by the National Natural Science Foundation of China under Grant No.11371001
文摘develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining with the greedy aug- previous ratio 3 to 1.8526.
基金funded by Deanship of Scientific Research,King Saud University,through the Vice Deanship of Scientific Research.
文摘Determining the optimum location of facilities is critical in many fields,particularly in healthcare.This study proposes the application of a suitable location model for field hospitals during the novel coronavirus 2019(COVID-19)pandemic.The used model is the most appropriate among the three most common location models utilized to solve healthcare problems(the set covering model,the maximal covering model,and the P-median model).The proposed nonlinear binary constrained model is a slight modification of the maximal covering model with a set of nonlinear constraints.The model is used to determine the optimum location of field hospitals for COVID-19 risk reduction.The designed mathematical model and the solution method are used to deploy field hospitals in eight governorates in Upper Egypt.In this case study,a discrete binary gaining–sharing knowledge-based optimization(DBGSK)algorithm is proposed.The DBGSK algorithm is based on how humans acquire and share knowledge throughout their life.The DBGSK algorithm mainly depends on two junior and senior binary stages.These two stages enable DBGSK to explore and exploit the search space efficiently and effectively,and thus it can solve problems in binary space.
文摘Facility location problem is a kind of NP-Hard combinational problem.Considering ever-changing demand sites,demand quantity and releasing cost,we formulate a model combining tabu search and FCM(fuzzy clustering method) to solve the capacitated dynamic facility location problem.Some results are achieved and they show that the proposed method is effective.
文摘The differential evolution algorithm is an evolutionary algorithm for global optimization and the un-capacitated facility location problem (UFL) is one of the classic NP-Hard problems. In this paper, combined with the specific characteristics of the UFL problem, we introduce the activation function to the algorithm for solving UFL problem and name it improved adaptive differential evolution algorithm (IADEA). Next, to improve the efficiency of the algorithm and to alleviate the problem of being stuck in a local optimum, an adaptive operator was added. To test the improvement of our algorithm, we compare the IADEA with the basic differential evolution algorithm by solving typical instances of UFL problem respectively. Moreover, to compare with other heuristic algorithm, we use the hybrid ant colony algorithm to solve the same instances. The computational results show that IADEA improves the performance of the basic DE and it outperforms the hybrid ant colony algorithm.
基金Supported by National Social Science Fund of China(23XGL039)。
文摘A novel location-queuing problem for blood collection facilities against MPHEs is studied in this paper.The decision variables to be determined include the opening plan of fixed blood collection rooms,the location of mobile blood collecting vehicles,and the number of service desks within facilities.This problem is formulated as a bi-objective multi-period integer nonlinear programming model,incorporating unique features that distinguish it from previous studies,such as pandemic risk,blood donation behavior,and the heterogeneity of blood collection facilities.The objectives are to minimize the total system cost and maximize donor satisfaction.To solve this problem,an improved multi-objective grey wolf optimization(IMOGWO)algorithm,which incorporates chaotic mapping and adaptive convergence factors,is proposed.Real data from Chongqing,China,is utilized to demonstrate the applicability of the model and the effectiveness of IMOGWO.Using evaluation metrics such as the C metric(CM),number of Pareto frontier(NPF),maximum spread(MS),spacing(SP),mean ideal distance(MID)and computation time(CPU time),numerical experiments demonstrate that the proposed IMOGWO outperforms non-dominated sorting genetic algorithm-Ⅱ(NSGA-Ⅱ),multi-objective particle swarm optimization(MOPSO),multi-objective whale optimization(MOWOA),multi-objective chimp optimization(MOCh OA),and multi-objective grey wolf optimization(MOGWO).
文摘Growing concerns about environmental quality of cities are calling for sustainable road transportation technologies. EV （electric vehicles）, for public and private transport, can contribute significantly to the lowering of the current pollution levels. However, the EV use is currently facing several weaknesses among which are： limited driving range, high cost and overall limited efficiency. Electric vehicles management is a relatively recent problem; its purpose is to expedite the establishment of a costumer convenient, cost-effective, EV infrastructure. Inspire the relevance of the problem, a few small research communities in this field work on some of its aspects. In this work, some important issues of this problem are discussed and the contribution of combinatorial optimization tools for solving some challenging subproblems is studied.
文摘Layout design problem is to determine a suitable arrangement for the departments so that the total costs associated with the flow among departments become least. Single Row Facility Layout Problem, SRFLP, is one of </span></span><span style="font-family:Verdana;"><span style="font-family:Verdana;"><span style="font-family:Verdana;">the </span></span></span><span><span><span style="font-family:""><span style="font-family:Verdana;">layout problems that have many practical applications. This problem and its specific scenarios are often used to model many of the raised issues in the field of facility location. SRFLP is an arrangement of </span><i><span style="font-family:Verdana;">n</span></i><span style="font-family:Verdana;"> departments with a specified length in a straight line so that the sum of the weighted distances between the pairs of departments is minimized. This problem is NP-hard. In this paper, first, a lower bound for a special case of SRFLP is presented. Then, a general </span><span style="font-family:Verdana;">case of SRFLP is presented in which some new and real assumptions are added to generate more practical model. Then a lower bound, as well as an algorithm, is proposed for solving the model. Experimental results on some instances in literature show the efficiency of our algorithm.
文摘The purpose of this review is to summarise the existing literature on the operational systems as to explain the current state of understanding on the coupled operational systems.The review only considers the linear optimisation of the operational systems.Traditionally,the operational systems are classified as decoupled,tightly coupled,and loosely coupled.Lately,the coupled operational systems were classified as systems of time-sensitive and time-insensitive operational cycle,systems employing one mix and different mixes of factors of production,and systems of single-linear,single-linear-fractional,and multi-linear objective.These new classifications extend the knowledge about the linear optimisation of the coupled operational systems and reveal new objective-improving models and new state-of-the-art methodologies never discussed before.Business areas affected by these extensions include product assembly lines,cooperative farming,gas/oil reservoir development,maintenance service throughout multiple facilities,construction via different locations,flights traffic control in aviation,game reserves,and tramp shipping in maritime cargo transport.
基金supported by the National Natural Science Foundation of China(No.11971252)。
文摘In the k-product uncapacitated facility location problem with penalties,we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened.There are k different kinds of products to be supplied by a set of open facilities.Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply.Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected.There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected.These service costs are assumed to be symmetric and satisfy the triangle inequality.The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities,servicing the clients,and the penalty is minimized.We address two different integer programs to describe the problem.Based on the linear programming rounding technique,we propose a(2k+1)-approximation algorithm for this problem.
基金supported by the National Natural Science Foundation of China(Nos.11971349,12071442,12371320,and 12371318).
文摘Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management science.In the CFLP,we have a potential facilities set and a clients set.Each facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be met.The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible.The CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants.Following this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty costs.As a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.
基金partly supported by the National Science Foundation of China under Grants 51008160China Postdoctoral Science Foundation (20080430686)+1 种基金Fundamental Research Funds for the Central Universities of China (NJAU: SKZK2015005)Talent Startup Fund of College of Engineering in NJAU of China (RCQD16-01)。
文摘Emergency response activity relies on transportation networks. Emergency facility location interacts with transportation networks clearly. This review is aimed to provide a combined framework for emergency facility location in transportation networks. The article reveals emergency response activities research clusters, issues, and objectives according to keywords co-occurrence analysis. Four classes of spatial separation models in transportation networks, including distance, routing, accessibility, and travel time are introduced. The stochastic and time-dependent characteristics of travel time are described. Travel time estimation and prediction method, travel time under emergency vehicle preemption,transportation network equilibrium method, and travel time in degradable networks are demonstrated. The emergency facilities location models interact with transportation networks, involving location-routing model, location models embedded with accessibility,location models embedded with travel time, and location models employing mathematical program with equilibrium constraints are reviewed. We then point out the-state-of-art challenges: ilities-oriented, evolution landscape and sequential decision modelling, datadriven optimization approach, and machine learning-based algorithms.
基金supported by National Natural Science Foundation of China(Grant Nos.60773185,10401038)Program for Beijing Excellent Talents(Grant No.20071D050150020S)
文摘In this paper,we consider the metric uncapacitated facility location game with service installation costs.Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.
基金supported by the National Natural Science Foundation of China under Grant Nos.60773185 and 11071268Program for Beijing Excellent Talents
文摘This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty. The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.
基金Supported by the National Natural Science Foundation of China(No.60773185,10401038) and Program for Beijing Excellent Talents
文摘We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.
基金Supported by the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No. 60325206the National Natural Science Foundation of China for Major International (Regional) Joint Research Project under Grant No. 60310213the National Natural Science Foundation of China under Grant No. 60573024.
文摘Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.
基金This research was supported by the National Natural Science Foundation of China(Nos.11901544 and 11801251).
文摘In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kinds of facilities located in k levels of hierarchy.The total cost including the facility cost,connection cost and penalty cost will be jointly paid by all the clients.In the corresponding game of the k-level facility location problem with penalties,called the k-level facility location game with penalties,the total cost should be allocated to different clients.This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic,competitive,and the approximate cost recovery is 6.
