Contributions to a Theory of Patrol Scheduling

The problem considered in this paper is that of scheduling police patrols in a random pattern. This involves generating patrol routes as well as schedules for dispatching patrol vehicles. A solution to this problem is obtained by specifying minimum average patrol requirements on each route segment in a network and then developing a procedure which meets these requirements while minimizing the total patrol effort. Introducing vehicles into the network in a Poisson stream results in Poisson streams in each route segment and so ensures that an observer cannot use previous history for predicting arrival patterns. This solution also has the property that the number of patrol cars in the network is a Poisson random variable for which the steady-state can be achieved immediately. The steady-state distribution function is also used to determine the number of patrol cars required.     

Scheduling programs with repetitive projects: A comparison of a simulated annealing,a genetic and a pair-wise swap algorithm

We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models.     

110警车配置及巡逻方案

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

The Feeder-bus Network-design Problem

The potential for improving the cost-effectiveness of public transport operations by designing better integrated feeder-bus/rail rapid transit systems has been widely recognized. This paper defines the feeder-bus network-design problem (FBNDP) as that of designing a feeder-bus network to access an existing rail system. The FBNDP is considered under two different demand patterns, many-to-one (M-to-1) and many-to-many (M-to-M). We present a mathematical programming model for the M-to-1 FBNDP, and show that it can be generalized to the M-to-M FBNDP. The FBNDP is a large and difficult vehicle-routeing-type problem with an additional decision variable—operating frequency. A heuristic model is presented, which generalizes the ‘savings approach’ to incorporate operating frequency. The computational analysis shows that the proposed heuristic provides reasonable feeder-bus networks and consistent responses to ‘what if’ questions. A comparison indicates that the proposed heuristic provides solutions that are superior to manually designed networks. The advantages of this heuristic are particularly significant under variable demand.     

Applying min–max <Emphasis Type="Italic">k</Emphasis> postmen problems to the routing of security guards

The most essential and alluring characteristic of a security estate is the estate's ability to provide 24-h security to its residents, of which the continual patrolling of roads and paths is vital. The objective of this paper is to address the lack of sufficient patrol route design procedures by presenting a tabu search algorithm capable of generating multiple patrol routes for an estate's security guards. The paper shows that the problem of designing these routes can be modelled as an Arc Routing Problem, specifically as min–max k postmen problems. The algorithm is illustrated with a real problem instance from an estate in Gauteng, South Africa. The patrol routes generated by the algorithm provide a significant improvement in the even patrolling of the road network, and a more balanced work distribution among guards. The algorithm is also tested on several benchmark problems from literature.     

Iterative algorithms for the curfew planning problem

The curfew planning problem is to design an annual timetable for railway track maintenance teams. Each team is capable of handling certain types of repairs and replacement jobs. The jobs are combined into a set of projects according to their locations and types. The timetable shows which project should be worked on by each team on a weekly basis throughout an entire year. Our objective is to design a schedule with minimum network disruption due to ongoing maintenance projects that require absolute curfew. Absolute curfew projects are those that cause complete closure of the rail traffic. For tackling this problem, we develop four optimization-based iterative algorithms. We also present very promising computational results obtained within a few minutes using data provided by a major North American railroad.     

Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

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.     

A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system

This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model’s comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.     

Approximating earliest arrival flows with flow-dependent transit times

For the earliest arrival flow problem one is given a network G=(V,A) with capacities u(a) and transit times τ(a) on its arcs a∈A, together with a source and a sink vertex s,t∈V. The objective is to send flow from s to t that moves through the network over time, such that for each time θ∈[0,T) the maximum possible amount of flow up to this time reaches t. If, for each θ∈[0,T), this flow is a maximum flow for time horizon θ, then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time θ depends on the flow on this particular arc at that time θ.For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each θ∈[0,T), need only α-times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on α; furthermore, we present a constant factor approximation algorithm for this problem.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

考虑货架存放期的经济批量排产问题的求解

在化工、造纸、制药、钢铁等工业生产中，一台设备或一条生产线可以生产多种产品的情况很常见。在生产中，如何安排各类产品的生产顺序以及生产数量显得十分重要。这类问题通常称作经济批量排产问题，这类问题是生产库存中的经典问题。本文研究的经济批量排产问题考虑了产品货架存放期因素，针对以往研究的不足，本文提出用批量变动方法求解该类问题，由计算结果显示，按照这种排产方法花费的成本要低于其他两种经济批量排产问题常用的方法。     

Scheduling healthcare services in a home healthcare system

We consider a scheduling problem in a home healthcare system in which nurses visit patients regularly for relatively minor healthcare services. Intervals between the visits may differ for different patients. On each day in the planning horizon, a nurse must visit the patients assigned to her/him on that day, and then return to the hospital. For the problem of determining the visiting schedule with the objective of minimizing total travel time of the nurse over the planning horizon, we develop a two-phase heuristic algorithm. To evaluate performance of the proposed algorithm, a series of computational tests is performed on a number of randomly generated problem instances and a real instance. Results of the tests show that the heuristic algorithm gives near optimal solutions for problems of practical sizes in a reasonable time.     

A GRASP-based approach for technicians and interventions scheduling for telecommunications

The Technicians and Interventions Scheduling Problem for Telecommunications embeds the scheduling of interventions, the assignment of teams to interventions and the assignment of technicians to teams. Every intervention is characterized, among other attributes, by a priority. The objective of this problem is to schedule interventions such that the interventions with the highest priority are scheduled at the earliest time possible while satisfying a set of constraints like the precedence between some interventions and the minimum number of technicians needed with the required skill levels for the intervention. We present a Greedy Randomized Adaptive Search Procedure (GRASP) for solving this problem. In the proposed implementation, we integrate learning to the GRASP framework in order to generate good-quality solutions using information brought by previous ones. We also compute lower bounds and present experimental results that validate the effectiveness of this approach.     

具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.     

Determining the Optimal Flows in Zero-Time Dynamic Networks

Here we are dealing with minimum cost flow problem on dynamic network flows with zero transit times and a new arc capacity, horizon capacity, which denotes an upper bound on the total flow traversing through on an arc during a pre-specified time horizon T. We develop a simple approach based on mathematical modelling attributes to solve the min-cost dynamic network flow problem where arc capacities and costs are time varying, and horizon capacities are considered. The basis of the method is simple and relies on the appropriate defining of polyhedrons, and in contrast to the other usual algorithms that use the notion of time expanded network, this method runs directly on the original network.     

Scheduling for single agile satellite,redundant targets problem using complex networks theory

Scheduling for the Earth observation satellites (EOSs) imaging mission is a complicated combinatorial optimization problem, especially for the agile EOSs (AEOSs). The increasing observation requirements and orbiting satellites have exacerbated the scheduling complexity in recent years. In this paper, the single agile satellite, redundant observation targets scheduling problem is studied. We introduce the theory of complex networks and find similarities between AEOS redundant targets scheduling problem and the node centrality ranking problem. Then we model this problem as a complex network, regarding each node as a possible observation opportunity, and define two factors, node importance factor and target importance factor, to describe the node/target importance. Based on the two factors, we propose a fast approximate scheduling algorithm (FASA) to obtain the effective scheduling results. Simulation results indicate the FASA is quite efficient and with broad suitability. Our work is helpful in the EOSs and AEOSs scheduling problems by using complex network knowledge.     

面向突发事件的安保巡逻选址-路径优化研究

安保巡逻任务要求以中心会场为保卫目标,进行指挥中心的选址、巡逻线路的规划。考虑区域环境、安保主体及突发事件对巡逻线路优化的影响,依据警方安保任务的规划流程,建立了多约束条件下安保指挥中心选址-巡逻路径规划的优化模型。设计了基于真实安保区域特征的安保中心模拟试验,各区域由专家依据CPTED理论进行评定分级,利用遗传算法求解并对结果进行了模拟检验,提出了基于整体应急水平最优的安保巡逻策略。     

Competitive production scheduling: A two-firm,noncooperative finite dynamic game

In this paper, we study the production scheduling problem in a competitive environment. Two firms produce the same product and compete in a market. The demand is random and so is the production capacity of each firm, due to random breakdowns. We consider a finite planning horizon. The scheduling problem is formulated as a finite dynamic game. Algorithms are developed to determine the security, hazard, and Nash policies. Numerical examples are discussed. A single-firm optimization model is also analyzed and it is observed that the production control policy from the single-firm optimization model may not perform well in a competitive environment.