A decomposition approach to solve a bilevel capacitated facility location problem with equity constraints

In this paper, we study a capacitated facility location problem with two decision makers. One (say, the leader) decides on which subset of facilities to open and the capacity to be installed in each facility with the goal of minimizing the overall costs; the second decision maker (say, the follower), once the facilities have been designed, aims at maximizing the profit deriving from satisfying the demands of a given set of clients beyond a certain threshold imposed by the leader. The leader can foresee but cannot control the follower’s behavior. The resulting mathematical formulation is a discrete–continuous bilevel optimization problem. We propose a decomposition approach to cope with the bilevel structure of the problem and the integrality of a subset of variables under the control of the leader. Such a proposal has been tested on a set of benchmark instances available in the literature.     

A column generation heuristic for districting the price of a financial product

This paper studies a districting problem that arises in the context of financial product pricing. The challenge lies in partitioning a set of small geographical regions into a set of larger territories. In each territory, the customers will share a common price. These territories need to be contiguous, contain enough customers and be as homogeneous as possible in terms of customer value. To address this problem, we present a column generation-based heuristic where the subproblem generates contiguous territories taken into account a nonlinear objective function. Computational results indicate that the territories produced by this heuristic are about 35% more homogeneous than those previously used in practice. The developed algorithm has been transferred to a financial firm and is now used to help craft more competitive financial products.     

Bilevel optimization applied to strategic pricing in competitive electricity markets

In this paper, we present a bilevel programming formulation for the problem of strategic bidding under uncertainty in a wholesale energy market (WEM), where the economic remuneration of each generator depends on the ability of its own management to submit price and quantity bids. The leader of the bilevel problem consists of one among a group of competing generators and the follower is the electric system operator. The capability of the agent represented by the leader to affect the market price is considered by the model. We propose two solution approaches for this non-convex problem. The first one is a heuristic procedure whose efficiency is confirmed through comparisons with the optimal solutions for some instances of the problem. These optimal solutions are obtained by the second approach proposed, which consists of a mixed integer reformulation of the bilevel model. The heuristic proposed is also compared to standard solvers for nonlinearly constrained optimization problems. The application of the procedures is illustrated in case studies with configurations derived from the Brazilian power system.     

Scheduling periodic customer visits for a traveling salesperson

The problem considered in this paper deals with determining daily routes for a traveling salesperson who provides customers in Upper Austria with product range information of a large, global food wholesaler. Each customer has to be visited at least once a year, with some customers requiring up to one visit per month. Further, some customers may not be visited each day of the week. Our decision support system uses a commercial GIS software to extract customer data for input into the optimization procedure and to visualize the results obtained by the algorithm. The optimization approach is based on the variable neighborhood search algorithm which assigns customers to days and determines routes for the salesperson for each day with the primary objective to minimize the total travel time of the salesperson. Another objective studied is to minimize the number of days needed by the salesperson to visit all customers in a given month. Further we analyze the effects of changes in the business environment like increases in the amount or flexibility of the salesperson’s working time and variations in the possible days for customer visits. Finally, we enrich the objective function by considering periodicity requirements for customer visits. Specifically, we penalize irregular schedules, where the time between two successive customer visits varies.     

Allocation of Marketing Effort Among <Emphasis Type="Italic">P</Emphasis> Substitutional Products in <Emphasis Type="Italic">N</Emphasis> Territories<Superscript>†</Superscript>

Frequently, companies face the problem of allocating a given marketing budget in order to maximize their total returns. In this paper we examine the problem of allocating marketing effort, such as advertising, among P substitutional products, distributed in N different sales territories. Two models are discussed. In the first model it is assumed that at most one product is promoted in each sales territory. It is shown that a simple algorithm leads to at least a local optimum in a finite number of steps. In the second model, the restriction of one product per territory is eliminated. Applying a concept of effective effort, the model is transformed to an equivalent separable programming problem, solvable by a “single-pass” algorithm for various forms of response functions. Furthermore, a concept of successive modifications of the objective function is discussed.     

A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem

The fleet size and mix vehicle routing problem consists of defining the type, the number of vehicles of each type, as well as the order in which to serve the customers with each vehicle when a company has to distribute goods to a set of customers geographically spread, with the objective of minimizing the total costs. In this paper, a heuristic algorithm based on tabu search is proposed and tested on several benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

Multiobjective scatter search for a commercial territory design problem

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A?territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem. The proposed metaheuristic is evaluated over a variety of instances taken from literature. This includes a comparison with two of the most successful multiobjective heuristics from literature such as the Scatter Tabu Search Procedure for Multiobjective Optimization (SSPMO) by Molina et al. (INFORMS J. Comput. 19(1):91?C100, 2007), and the Non-dominated Sorting Genetic Algorithm (NSGA-II) by Deb et?al. (Parallel problem solving from nature ?C PPSN VI, Lecture notes in computer science, vol. 1917, Springer, Berlin, pp.?849?C858, 2000). Experimental work reveals that the proposed procedure consistently outperforms both heuristics, SSPMO and NSGA-II, on all instances tested.     

On a class of bilevel linear mixed-integer programs in adversarial settings

We consider a class of bilevel linear mixed-integer programs (BMIPs), where the follower’s optimization problem is a linear program. A typical assumption in the literature for BMIPs is that the follower responds to the leader optimally, i.e., the lower-level problem is solved to optimality for a given leader’s decision. However, this assumption may be violated in adversarial settings, where the follower may be willing to give up a portion of his/her optimal objective function value, and thus select a suboptimal solution, in order to inflict more damage to the leader. To handle such adversarial settings we consider a modeling approach referred to as \(\alpha \)-pessimistic BMIPs. The proposed method naturally encompasses as its special classes pessimistic BMIPs and max–min (or min–max) problems. Furthermore, we extend this new modeling approach by considering strong-weak bilevel programs, where the leader is not certain if the follower is collaborative or adversarial, and thus attempts to make a decision by taking into account both cases via a convex combination of the corresponding objective function values. We study basic properties of the proposed models and provide numerical examples with a class of the defender–attacker problems to illustrate the derived results. We also consider some related computational complexity issues, in particular, with respect to optimistic and pessimistic bilevel linear programs.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

An efficient evolutionary algorithm for the ring star problem

This paper addresses the ring star problem (RSP). The goal is to locate a cycle through a subset of nodes of a network aiming to minimize the sum of the cost of installing facilities on the nodes on the cycle, the cost of connecting them and the cost of assigning the nodes not on the cycle to their closest node on the cycle. A fast and efficient evolutionary algorithm is developed which is based on a new formulation of the RSP as a bilevel programming problem with one leader and two independent followers. The leader decides which nodes to include in the ring, one follower decides about the connections of the cycle and the other follower decides about the assignment of the nodes not on the cycle. The bilevel approach leads to a new form of chromosome encoding in which genes are associated to values of the upper level variables. The quality of each chromosome is evaluated by its fitness, by means of the objective function of the RSP. Hence, in order to compute the value of the lower level variables, two optimization problems are solved for each chromosome. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time. A study to select the best configuration of the algorithm is presented. The algorithm is tested on a set of benchmark problems providing very accurate solutions within short computing times. Moreover, for one of the problems a new best solution is found.     

A novel maximum dispersion territory design model arising in the implementation of the WEEE-directive

The problem discussed in this paper is motivated by the new recycling directive Waste Electrical and Electronic Equipment of the European Commission. The core of this law is, that each company which sells electrical or electronic equipment in a European country has the obligation to recollect and recycle an amount of returned items which is proportional to its market share. To assign collection stations to companies, in Germany for one product type a territory design approach is planned. However, in contrast to classical territory design, the territories should be geographically as dispersed as possible to avoid that a company, respectively its logistics provider responsible for the recollection, gains a monopoly in some region. First, we identify an appropriate measure for the dispersion of a territory. Afterwards, we present a first mathematical programming model for this new problem as well as a solution method based on the Greedy Randomized Adaptive Search Procedure methodology. Extensive computational results illustrate the suitability of the model and assess the effectiveness of the heuristic.     

Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network

This paper addresses a generalization of the capacitated location-routing problem (CLRP) arising in the design of a collection network for a company engaged in collecting used products from customer zones. The company offers customers a financial incentive per unit of used products. This incentive determines the quantity of used products which are returned by customers. Moreover, it is not necessary for the company to visit all customer zones or to collect all returns in each visited customer zone. The objective is to simultaneously find the location of collection centers, the routes of vehicles, the value of incentive offered and the amount of used products collected from customer zones, so as to maximize the company's overall profit. We develop two mixed integer linear programming formulations of the problem and a heuristic algorithm based on iterated local search. Extensive computational experiments on this problem demonstrate the effectiveness of the proposed algorithm.     

考虑人员培训的任务指派问题模型及算法

随着劳动力成本的快速增长,越来越多的企业选择雇佣兼职员工。本文研究了中国一家家居企业的任务指派问题,该任务指派问题的特点是一个任务由多个子任务组成,并在安排时需要同时考虑人员培训和满足客户的服务时间的要求,该问题的目标是安排尽可能多的家装任务并获得尽可能多的收益。为了解决该问题,本文建立了整数规划模型,并设计高效的局部分支算法对模型进行求解。为了获得最佳的求解效果,我们实验分析了不同的分支变量和参数设置对算法性能的影响,并获得了最佳的参数设置。特别的,我们发现有效分支变量的选择与问题特点相关。实验还表明,在相同求解时间内,在13个算例中,局部分支算法在9个算例上的表现优于Gurobi。     

Branch-and-price and constraint programming for solving a real-life technician dispatching problem

We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. A branch-and-price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with constraint programming in the column generation phase. The column generation takes advantage of the fact that each technician can satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice.     

Integrating link-based discrete credit charging scheme into discrete network design problem

In this paper, we present an optimization model for integrating link-based discrete credit charging scheme into the discrete network design problem, to improve the transport performance from the perspectives of both transport network planning and travel demand management. The proposed model is a mixed-integer nonlinear bilevel programming problem, which includes an upper level problem for the transport authority and a lower level problem for the network users. The lower level sub-model is the traffic network user equilibrium (UE) formulation for a given network design strategy determined by the upper level problem. The network user at the lower level tries to minimize his/her own generalized travel cost (including both the travel time and the value of the credit charged for using the link) by choosing his/her route. While the transport authority at the upper level tries to find the optimal number of lanes and credit charging level with their locations to minimize the total system travel time (or maximize the transportation system performance). A genetic algorithm is used to solve the proposed mixed-integer nonlinear bilevel programming problem. Numerical experiments show the efficiency of the proposed model for traffic congestion mitigation, reveal that interaction effects across the tradable credit scheme and the discrete network design problem which amplify their individual effects. Moreover, the integrated model can achieve better performance than the sequential decision problems.     

A neural network for solving a convex quadratic bilevel programming problem

A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the equilibrium, which corresponds to the optimal solution of a convex quadratic bilevel programming problem. Numerical simulation results show that the proposed neural network is feasible and efficient for a convex quadratic bilevel programming problem.     

Fuzzy bilevel programming with multiple objectives and cooperative multiple followers

Classic bilevel programming deals with two level hierarchical optimization problems in which the leader attempts to optimize his/her objective, subject to a set of constraints and his/her follower’s solution. In modelling a real-world bilevel decision problem, some uncertain coefficients often appear in the objective functions and/or constraints of the leader and/or the follower. Also, the leader and the follower may have multiple conflicting objectives that should be optimized simultaneously. Furthermore, multiple followers may be involved in a decision problem and work cooperatively according to each of the possible decisions made by the leader, but with different objectives and/or constraints. Following our previous work, this study proposes a set of models to describe such fuzzy multi-objective, multi-follower (cooperative) bilevel programming problems. We then develop an approximation Kth-best algorithm to solve the problems.     

Salespeople's management of customer information: Impact on optimal territory and sales force sizes

Collecting and processing territory and account information are major aspects of a salesperson's task. To a large extent, salespeople's effectiveness depends on the amount and quality of the market information available to them (such as their customers' needs and potential, the likelihood of getting an order after some contact time, etc.). Although they are not always easy to disentangle, these information gathering and processing activities on one hand, and the effective contact time devoted to selling to clients and prospects on the other, vie for the limited time resources available to a salesperson. This paper provides a simple statistical procedure for estimating the costs of information gathering and processing by a salesperson. The model can be used by management for estimating the most profitable territory size to be assigned to each salesperson, and consequently for estimating the optimal sales force size.     

Mathematical structure of a bilevel strategic pricing model

This paper is concerned with the characterization of optimal strategies for a service firm acting in an oligopolistic environment. The decision problem is formulated as a leader–follower game played on a transportation network, where the leader firm selects a revenue-maximizing price schedule that takes explicitly into account the rational behavior of the customers. In the context of our analysis, the follower’s problem is associated with a competitive network market involving non atomic customer groups. The resulting bilevel model can therefore be viewed as a model of product differentiation subject to structural network constraints.