Electric vehicles: effect of the availability threshold on the transportation cost

This paper addresses the transportation problem using public electric cars. The management of this new form of transportation means considering two issues: the redistribution of the cars among the stations (in this paper, we assume that this issue is perfectly settled, the number of cars needed at each station being available at any time), and the recharge problem that we describe in this paper. At each station, a decision concerning the cars which should become available to customers, has to be taken. We assume that a vehicle is available when its charge is greater than a given threshold. Our goal is to optimize this threshold. Copyright © 1999 John Wiley & Sons, Ltd.     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Service network design for freight railway transportation: the Italian case

In this paper, we present a case study on freight railway transportation in Italy, which is a by-product of research collaboration with a major Italian railway company. We highlight the main features of the Italian reality and propose a customized mathematical model to design the service network, that is, the set of origin-destination connections. More specifically, the model suggests the services to provide, the number of trains travelling on each connection, the number of cars and their type. We consider both full and empty freight car movements and take handling costs into account. All decisions are taken in order to minimize the total costs. The quality of service is guaranteed by satisfying all the transportation demand and by implicitly minimizing the waiting time of cars at intermediate railway stations. Our approach yields to a multi-commodity network design problem with a concave cost function. To solve this problem, we implement a specialized tabu search procedure. Computational results on realistic instances show a significant improvement over current practice.     

基于多元线性回归分析和Chan算法的三维精确定位研究

基于无线通信基站的室内三维定位问题主要是在已知TOA和基站三维信息的情况计算出终端的位置信息,实际上就是求解方程组中的未知数.首先建立通用模型和算法求解出终端的定位,接着通过优化得到使用尽量少的基站数目实现近似最优精度的定位,然后利用提出的算法实现终端移动轨迹的二维定位,最后结合实际情况,考虑了基站的有效测量距离并设计了有效基站识别算法对问题进行了分析.     

Server allocation for zero buffer tandem queues

In this paper we consider the problem of allocating servers to maximize throughput for tandem queues with no buffers. We propose an allocation method that assigns servers to stations based on the mean service times and the current number of servers assigned to each station. A number of simulations are run on different configurations to refine and verify the algorithm. The algorithm is proposed for stations with exponentially distributed service times, but where the service rate at each station may be different. We also provide some initial thoughts on the impact on the proposed allocation method of including service time distributions with different coefficients of variation.     

Balancing assembly lines with variable parallel workplaces: Problem definition and effective solution procedure

Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line subject to a strict or average cycle time. Traditionally, stations are considered to be manned by one operator, respectively, or duplicated in form of identical parallel stations, each also manned by a single operator. In practice, this assumption is usually too restrictive. This is particularly true for large products like cars, trucks, busses and machines, which can be handled by several operators performing different tasks at the same time. Only restricted research has been done on such parallel workplaces within the same station though they have significant relevance in real-world assembly line settings.     

R-SALSA: A branch,bound, and remember algorithm for the workload smoothing problem on simple assembly lines

We consider a simple assembly line balancing problem with given cycle time and number of stations. A quadratic objective function based on a so-called smoothness index SX levels the workloads of the stations. For this problem, called SALBP-SX, only a few solution procedures have been proposed in literature so far. In this paper, we extend and improve the branch-and-bound procedure SALSA (Simple Assembly Line Smoothing Algorithm) of Walter et al. (2021) to a bidirectional branch, bound, and remember algorithm called R-SALSA (R for remember). Like SALSA, it is based on a dynamic programming scheme which pre-determines potential workloads of the stations and provides a construction plan for possible station loads. This scheme is extended by the new concept of supporters and preventers which significantly enhances branching, bounding, and logical tests. Furthermore, a tailored heuristic that searches for improved initial solutions, a bidirectional branching scheme and additional dominance rules are integrated. In extensive computational experiments, we find out that our new procedure clearly outperforms all former exact solution procedures on benchmark data sets with up to 1000 tasks.     

A large scale machine loading problem in flexible assembly

Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.     

Optimal network configuration and capacity expansion of railroads

Railroads ship individual cars according to blocking plans that route the cars in groups (blocks) that share common intermediate stops. An individual shipment is regrouped (reclassified) two to three times along the way from its origin to destination. Yards are crucial facilities of the rail network where cars are reclassified according to such blocking plans. Therefore, yard locations and the blocking plan impose the detour and classification of cars over the physical network. Yards are capacitated with respect to number of blocks made and number of cars classified; rail lines between major stations are capacitated with respect to number of cars that pass through. These restrictions are accounted for in designing the blocking plans. Changing the yard locations and expanding associated capacities may result in dramatic changes in blocking plans saving tens of millions of dollars in railroad transportation costs. We develop a mathematical programming formulation and propose solution methods for the yard location problem and the capacity expansion problems. We demonstrate that the railroads can save significantly by reconfiguring their networks.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

共享单车调度优化问题研究

针对共享单车站点经常出现的供需不平衡问题,提出人工调度策略,以提高单车利用率和用户满足率.首先将一天划分为几个用车高峰时段,根据每个站点的单车使用历史数据,计算各站点在每个时段的需求量区间;在区域内单车总投放量不变的前提下,基于每个时段初期各个站点存放的单车数量,确定单车调出站点和单车调入站点,进一步以站点之间的单车调度数量为决策变量,建立共享单车调度问题的整数规划模型,使区域内各个单车站点的供需量基本达到平衡,并且总调度成本最小.利用北京市海淀区共享单车数据进行模拟计算,对比分析了调度优化前后的共享单车利用率和用户满足率.结果显示,调度优化后,单车利用率平均提高7.78%,用户满足率平均提高13.09%;综合考虑企业调度成本和收入情况可以发现,通过调度优化,企业的平均利润增长率为7.53%.本文的研究结果可以帮助共享单车企业提升管理水平,增加利润.     

Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

A multi-period double coverage approach for locating the emergency medical service stations in Istanbul

We consider the multi-period location planning problem of emergency medical service (EMS) stations. Our objective is to maximize the total population serviced by two distinct stations within two different response time limits over a multi-period planning horizon. Our aim is to provide a backup station in case no ambulance is available in the closer station and to develop a strategic plan that spans multiple periods. In order to solve this problem, we propose a Tabu Search approach. We demonstrate the effectiveness of the proposed approach on randomly generated data. We also implement our approach to the case of Istanbul to determine the locations of EMS stations in the metropolitan area.     

110警车配置及巡逻方案

针对110警车调度问题,引入了图论中的最短路算法以及计算几何的相关理论,建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型.另外,用C++编写了一个可视化的软件,不仅实现了手动描点,自动求出覆盖线段集合的功能,同时利用计算机模拟警车的巡逻路线,最后通过计算机检验得到结果,其合理性和实用性都令人满意.针对问题一,通过人机结合,配置17辆警车就能实现D1的目标,很好地兼顾了警车巡逻的运行成本,减少公安部门车辆和人员等的投入.针对问题二,采用模糊数学相关理论使评价指标实现了从定性到定量的转变.针对问题三和六,在D1的基础上,兼顾了巡逻效果的显著性,采用最少被巡逻道路优先的贪心算法建立了动态巡逻模型,得到了合理的巡逻方案.在此方案中,我们动用了30辆警车完成了问题一的目标.另外还额外考虑了案发事件概率不均匀分布的情况,建立了改进模型.针对问题四,在完成问题三指标的基础上,为了尽可能提高巡逻车辆的隐蔽性和增强巡逻效果,采用轮盘赌算法来引入随机性.针对问题五,采用最远距离道路优先贪心策略,使模型尽可能满足条件D1,D2.针对问题七,提出了一些额外因素及其解决方案,进一步完善了模型,使模型更贴近现实.     

An Operational Research Approach to Allocation of Clients to a Certain Class of Service Institutions

A model is developed to explain the allocation of clients to different locations of a certain class of service institutions. It can be used for all types of allocation-problems which have the features: clients are travelling from their home locations to the service places. They can choose among several locations of the institution all of which offer the same services. The clients need constant travelling times or costs, and they cause different waiting times or costs at each location, which are a function of the number of clients choosing that service station. The objective of the individual client is to minimize the total time or cost required.Since exact alogrithms cannot be used because of the large number of variables and the non-linearity of the problem, a special approximation algorithm is developed.The paper presents the results of a study concerning the allocation of cars, which must periodically be checked for traffic safety at official test stations.     

Automated antenna positioning algorithms for wireless fixed-access networks

This article addresses a real-life problem - obtaining communication links between multiple base station sites, by positioning a minimal set of fixed-access relay antenna sites on a given terrain. Reducing the number of relay antenna sites is considered critical due to substantial installation and maintenance costs. Despite the significant cost saved by eliminating even a single antenna site, an inefficient manual approach is employed due to the computational complexity of the problem. From the theoretical point of view we show that this problem is not only NP hard, but also does not have a constant approximation. In this paper we suggest several alternative automated heuristics, relying on terrain preprocessing to find educated potential points for positioning relay stations. A large-scale computer-based experiment consisting of approximately 7,000 different scenarios was conducted. The quality of alternative solutions was compared by isolating and displaying factors that were found to affect the standard deviation of the solutions supplied by the tested heuristics. The results of the simulation based experiments show that the saving potential increases when more base stations are needed to be interconnected. The designs of a human expert were compared to the automatically generated solutions for a small subset of the experiment scenarios. Our studies indicate that for small networks (e.g., connecting up to ten base stations), the results obtained by human experts are adequate although they rarely exceed the quality of automated alternatives. However, the process of obtaining these results in comparison to automated heuristics is longer. In addition, when more base station sites need to be interconnected, the human approach is easily outperformed by our heuristics, both in terms of better results (fewer antennas) and in significant shorter calculation times.     

Optimal workforce assignment to operations of a paced assembly line

We study a paced assembly line intended for manufacturing different products. Workers with identical skills perform non-preemptable operations whose assignment to stations is known. Operations assigned to the same station are executed sequentially, and they should follow the given precedence relations. Operations assigned to different stations can be performed in parallel. The operation’s processing time depends on the number of workers performing this operation. The problem consists in assigning workers to operations such that the maximal number of workers employed simultaneously in the assembly line is minimized, the line cycle time is not exceeded and the box constraints specifying the possible number of workers for each operation are not violated. We show that the general problem is NP-hard in the strong sense, develop conventional and randomized heuristics, propose a reduction to a series of feasibility problems, present a MILP model for the feasibility problem, show relation of the feasibility problem to multi-mode project scheduling and multiprocessor scheduling, establish computational complexity of several special cases based on this relation and provide computer experiments with real and simulated data.     

On-off scheduling schemes for power-constrained electric vehicle charging

In this paper, we study the problem of establishing a dynamic charging schedule of electric vehicles (EVs) at a charging station, assuming that limited power implies that only a limited number of EVs can charge simultaneously. The only control we assume to be available to the charging station is the ability to (at any given time) turn on or off the power supply to any EV, with this tool we want to develop a charging schedule that will satisfy the energy demands of the EVs in their intended deadlines. We propose two distinct approaches to this problem: a discretized time version, based on a greedy-like algorithm, and a continuous time version, based on linear programming. We compare these two approaches and numerically study the improvement they yield in the efficiency of the charging procedure, when applied to simulated data based on real parking data. Finally, we illustrate the flexibility of the models by sketching several possible extensions.     

A fuzzy clustering application to precise orbit determination

In recent years, fuzzy logic techniques have been successfully applied in geodesy problems, in particular to GPS. The aim of this work is to test a fuzzy-logic method with an enhanced probability function as a tool to provide a reliable criteria for weighting scheme for satellite-laser-ranging (SLR) station observations, seeking to optimize their contribution to the precise orbit determination (POD) problem. The data regarding the stations were provided by the International Laser Ranging Service (ILRS), NASA/Crustal Dynamics Data Information System (CDDIS) provided the satellite data for testing the method. The software for processing the data is GEODYN II provided by NASA/Goddard Space Flight Center (GSFC). Factors to be considered in the fuzzy-logic clustering are: the total number of LAGEOS passes during the past 12 months, the stability measure of short- and long-term biases, the percentage of LAGEOS normal points that were accepted in CSR weekly LAGEOS analysis, and the RMS uncertainty of the station coordinates. A fuzzy-logic statistical method allows classifying the stations through a clear ‘degree of belonging’ to each station group. This degree of belonging translates into a suitable weight to be assigned to each station in the global solution. The first tests carried out showed improvements in the RMS of the global POD solution as well as individual stations, to within a few millimeters. We expect further work would lead to further improvements.