A bi-objective turning restriction design problem in urban road networks

This paper introduces a bi-objective turning restriction design problem (BOTRDP), which aims to simultaneously improve network traffic efficiency and reduce environmental pollution by implementing turning restrictions at selected intersections. A bi-level programming model is proposed to formulate the BOTRDP. The upper level problem aims to minimize both the total system travel time (TSTT) and the cost of total vehicle emissions (CTVE) from the viewpoint of traffic managers, and the lower level problem depicts travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. The modified artificial bee colony (ABC) heuristic is developed to find Pareto optimal turning restriction strategies. Different from the traditional ABC heuristic, crossover operators are captured to enhance the performance of the heuristic. The computational experiments show that incorporating crossover operators into the ABC heuristic can indeed improve its performance and that the proposed heuristic significantly outperforms the non-dominated sorting genetic algorithm (NSGA) even if different operators are randomly chosen and used in the NSGA as in our proposed heuristic. The results also illustrate that a Pareto optimal turning restriction strategy can obviously reduce the TSTT and the CTVE when compared with those without implementing the strategy, and that the number of Pareto optimal turning restriction designs is smaller when the network is more congested but greater network efficiency and air quality improvement can be achieved. The results also demonstrate that traffic information provision does have an impact on the number of Pareto optimal turning restriction designs. These results should have important implications on traffic management.     

Turning restriction design in traffic networks with a budget constraint

The restriction (prohibition) of certain turns at intersections is a very common task employed by the managers of urban traffic networks. Surprisingly, this approach has received little attention in the research literature. The turning restriction design problem (TRDP) involves finding a set of turning restrictions at intersections to promote flow in a congested urban traffic network. This article uses a successive linear approximation (SLA) method for identifying approximate solutions to a nonlinear model of the TRDP. It aims to adjust the current turning restriction regime in a given network in order to minimize total user travel cost when route choice is driven by user equilibrium principles. Novel features of the method include the facts that it is based on link capacity-based arc travel costs and there is a budget constraint on the total cost of all turning restriction alterations. It has been tested using standard network examples from the literature. One of the tests utilized a multi-start approach which improved the solutions produced by the SLA method. The method was also employed to identify turning restrictions for an actual medium-sized urban traffic network in Brazil. Computational experience with the proposed method is promising.     

ATIS和道路收费下混合SUE相对于SSO的效率损失

在ATIS和道路收费共同作用的异质性交通网络中,基于用户在信息接受程度与时间价值上的异质性,对用户进行合理分类,所有用户均按照随机方式进行择路.构建了多用户混合随机均衡等价的变分不等式模型,以及多用户随机社会最优模型.以用户感知的总出行成本作为系统性能评价的指标,当收费作为系统总成本的一部分时,分别在时间准则与费用准则下研究了多用户混合随机均衡相对于随机社会最优的绝对效率损失问题.研究结果表明,时间准则下的绝对效率损失上界与路段出行时间函数和混合随机均衡时系统的实际总出行时间有关,费用准则下的绝对效率损失上界还与出行者的社会经济特性和随机社会最优时系统的实际总出行时间有关.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems

The k-center problem arises in many applications such as facility location and data clustering. Typically, it is solved using a branch and bound tree traversed using the depth first strategy. The reason is its linear space requirement compared to the exponential space requirement of the breadth first strategy. Although the depth first strategy gains useful information fast by reaching some leaves early and therefore assists in pruning the tree, it may lead to exploring too many subtrees before reaching the optimal solution, resulting in a large search cost. To speed up the arrival to the optimal solution, a mixed breadth-depth traversing strategy is proposed. The main idea is to cycle through the nodes of the same level and recursively explore along their first promising paths until reaching their leaf nodes (solutions). Thus many solutions with diverse structures are obtained and a good upper bound of the optimal solution can be achieved by selecting the minimum among them. In addition, we employ inexpensive lower and upper bounds of the enclosing balls, and this often relieves us from calling the computationally expensive exact minimum enclosing ball algorithm. Experimental work shows that the proposed strategy is significantly faster than the naked branch and bound approach, especially as the number of centers and/or the required accuracy increases.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

Assignment of add–drop multiplexer (ADM) rings and digital cross-connect system (DCS) mesh in telecommunication networks

This paper discusses a design of a hybrid ring–mesh network in a survivable communication network. Given a set of traffic demands, the problem is to assign each traffic demand to rings and mesh such that the cost of add–drop multiplexer (ADM) and digital cross-connect system (DCS) equipment required is minimized. This assignment problem can be considered together with the fibre routing of nodes on rings and mesh. As a solution procedure, a tabu search is developed with recency-based short-term and frequency-based long-term memory structures. In computational experiments, the proposed tabu search is compared with the solutions obtained by the branch and bound procedure of CPLEX. We see that the tabu search provides a nearly optimal solution within sufficiently short time periods for all test problems with a gap of approximately 1–4% from the lower bound.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

Admission control for a multi-server queue with abandonment

In a M/M/N+M queue, when there are many customers waiting, it may be preferable to reject a new arrival rather than risk that arrival later abandoning without receiving service. On the other hand, rejecting new arrivals increases the percentage of time servers are idle, which also may not be desirable. We address these trade-offs by considering an admission control problem for a M/M/N+M queue when there are costs associated with customer abandonment, server idleness, and turning away customers. First, we formulate the relevant Markov decision process (MDP), show that the optimal policy is of threshold form, and provide a simple and efficient iterative algorithm that does not presuppose a bounded state space to compute the minimum infinite horizon expected average cost and associated threshold level. Under certain conditions we can guarantee that the algorithm provides an exact optimal solution when it stops; otherwise, the algorithm stops when a provided bound on the optimality gap is reached. Next, we solve the approximating diffusion control problem (DCP) that arises in the Halfin–Whitt many-server limit regime. This allows us to establish that the parameter space has a sharp division. Specifically, there is an optimal solution with a finite threshold level when the cost of an abandonment exceeds the cost of rejecting a customer; otherwise, there is an optimal solution that exercises no control. This analysis also yields a convenient analytic expression for the infinite horizon expected average cost as a function of the threshold level. Finally, we propose a policy for the original system that is based on the DCP solution, and show that this policy is asymptotically optimal. Our extensive numerical study shows that the control that arises from solving the DCP achieves a very similar cost to the control that arises from solving the MDP, even when the number of servers is small.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

ATIS和道路收费下的混合随机用户均衡的效率损失

在ATIS作用下的交通网络中,用户在交通信息的接受程度上是异质的;考虑到装有ATIS的用户并不总是遵循ATIS的建议,因此,引入信息遵从率这一参数,将所有用户分为三类:安装并遵从信息、安装但不遵从信息和不安装的用户;均按照随机用户均衡的方式进行择路,但对出行时间有不同的感知。同时考虑存在道路收费的情形下,用户在时间价值上是异质的。综合考虑交通信息与道路收费的影响,基于用户两方面的异质性,对其进行合理分类,构建了多用户多准则的混合随机均衡模型及其等价的变分不等式;当收费不作为系统总成本的一部分时,建立了时间准则与费用准则下的系统最优模型;在此基础之上,分别研究了两种准则下混合均衡相对于系统最优的效率损失,给出了效率损失上界,并进一步分析了效率损失上界与各参数间的关系;交通管理者可以从道路收费策略的实施、信息诱导系统的完善等角度进行路网的改造和优化设计。     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.     

Optimal control of assignment of jobs to processors under heavy traffic

The paper is concerned with the optimal control of the assignment of jobs from several arriving random streams to one of a bank of processors. Owing to the difficulty of the general problem, a heavy traffic approach is used. The required work depends on the processor to which it is assigned. The information that the assignment can be based on is quite flexible, and several information structures (data on which the control is based) are considered. The assignment can be made on arrival or when the job is to be processed. There can be bursty arrivals (the bursts depending on randomly varying environmental factors), rather general nonlinear cost functions and other complications. It is shown, under reasonably general conditions, that the optimal costs for the physical systems converge to the optimal cost for the heavy traffic limit problem, as the heavy traffic parameter goes to its limit. Numerical data is presented to illustrate some of the potential uses of the limit process for obtaining optimal contros, or controls satisfying optimal tradeoffs among competing criteria. The methods of proof are quite powerful tools for such optimal control problems     

A branch and bound algorithm for minimizing the expected cost of testing coherent systems

We are interested in the problem of minimizing the expected cost of testing a coherent system. The concept of the Importance of Components is used to develop a branch and bound algorithm which determines the optimal testing policy for any coherent system.     

An algorithm for the min concave cost flow problem

A method is presented to solve that class of network flow problems, which may be formulated as one source - multiple destination minimum cost flow problems with concave costs. The global optimum is searched using a branch and bound procedure, in which the enumeration scheme is based on a characterization of the optimal solution set, while linear relaxations of the original problem provide lower bounds.     

Single machine scheduling under market uncertainty

This paper considers single machine scheduling problems where job processing times are known and deterministic but where the reward received upon completion of a job changes stochastically over time according to Brownian motion. The objectives of maximizing expected net-present-value (NPV), minimizing the variance of NPV and maximizing the probability of achieving a minimum benchmark NPV are considered. For non-preemptive static list policies complexity results and branch and bound procedures are presented. The branch and bound procedures are shown to be effective for problem instances with 20–25 jobs. For the problem of maximizing NPV with non-preemptive dynamic policies the optimal static schedule is shown through empirical testing to be as good as a greedy heuristic and to be near optimal when the variance is not large.