海运服务链中的运力定价和空箱调运责任研究

本文研究了单个承运商和两个货运代理在双向港口间提供往返货运服务的航运服务链。由于港口间货运需求的内在不平衡,货运公司在多港口间的空箱调运会产生巨大的空箱调运费用。分别构建了承运商承担和承运商与货运代理共同承担空箱调运的数学模型,通过数学模型和数值算例分析了不同市场条件下的空箱调运责任和运力定价策略。研究发现承运商和货运代理是否采用定价策略来平衡需求取决于双向港口间货运市场的潜在需求差异。同时,承运商与货运代理的空箱调运分摊为非此即彼策略,当空箱调运成本大于某阈值时,承运商独自承担空箱调运责任;反之,货运代理承担空箱调运责任。而且货运代理承担模式增加整个海运链的利润,但进一步加剧空箱的不平衡状况。     

考虑多仓库的共享单车重新配置问题研究

共享单车是我国大力提倡的低碳交通出行模式,加快共享单车发展是解决最后一公里、城市拥堵和环境污染等问题的重要途径。由于人们停放共享单车的无规律性,使得共享单车系统中各车桩的单车库存量存在不平衡。如何合理的对车桩中的单车进行重新调配,来满足用户的需求,是相关企业亟待解决的问题。共享单车的调配路线优化是优化车桩库存量的重要手段之一。本文研究多仓库条件下的货车调配路线优化问题,建立了一个混合整数非线性规划模型。不同于传统的路径优化问题的研究大多是以成本或时间为目标,本文采用基于车桩库存量的非线性惩罚函数来表示用户需求,从而使得所研究的问题是一个凸函数优化问题。为了简化本文的问题,将目标函数分段线性化。基于车桩网络的特点,设计了变邻域搜索算法,以及构建初始解的贪婪算法。最后,以某共享单车公司为例,进行算例分析,来说明模型和算法的合理性和有效性。     

Optimal empty vehicle repositioning and fleet-sizing for two-depot service systems

This paper considers the problem of determining optimal control policies for empty vehicle repositioning and fleet-sizing in a two-depot service system with uncertainties in loaded vehicle arrival at depots and repositioning times for empty vehicles in the fleet. The objective is to minimise the sum of the costs incurred by vehicle maintenance, empty vehicle repositioning and vehicle leasing. A novel integrated model is presented. The optimal empty repositioning policy for a particular fleet size is shown to be of the threshold control type. The explicit form of the cost function under such threshold controls is obtained. The optimal threshold values and fleet-size are then derived. Numerical examples are given to demonstrate the results.     

存在空箱调运的非对称运输市场定价策略研究

考虑空箱调运成本,本文对垄断和双寡头市场分别研究运输企业在两条相向路径上的定价问题。对于垄断市场,建立了运输企业最优定价策略,并刻画出无空箱调运的潜在需求不平衡区间。对于双寡头市场,考虑同一路径上不同企业潜在运输需求不等的现实情境,求解了非对称企业的伯川德纳什均衡,给出最优定价策略。研究发现,无空箱调运并不意味着较高利润,运输企业没有必要刻意消除空箱调运现象。另外,增加单位载货运输成本和竞争强度会降低企业利润,而提升单位空箱重置成本、价格敏感度和市场不对称程度都会增大企业利润。     

Dynamic repositioning for vehicle sharing with setup costs

This study considers a multi-period two-region repositioning problem with setup repositioning costs involved for vehicle sharing systems. We find that incorporating such costs can influence the total cost significantly and complicate the structure of the optimal policy. Moreover, we manage to partially characterize the optimal policy, and then develop an easy-to-implement heuristic policy. The performance of the heuristic policy and the influence of setup repositioning costs on policies are assessed numerically.     

Optimal control of a single server in a finite-population queueing network

We study the optimal dynamic assignment of a single server to multiple stations in a finite-population queueing network. The objective is to maximize the long-run average reward/throughput. We use sample-path comparisons to identify conditions on the network structure and service time distributions under which the optimal policy is an index policy. This index policy assigns the server to the non-empty station where it takes the shortest amount of time (in some stochastic sense) to complete a job. For example, in a network of multiple parallel stations, the optimal policy assigns the highest priority to the fastest station if service times can be ordered in likelihood ratios. Finally, by means of a numerical study, we test the shortest-expected-remaining-service-time policy on parallel-series networks with three stations and find that this index policy either coincides with the optimal policy or provides a near-optimal performance.     

A two-phase heuristic approach to the bike repositioning problem

An approach to overcome the bike imbalance problem is to transfer excess bikes to branches with bike shortages. This study develops a constrained mathematical model to deal with a multi-vehicle bike-repositioning problem, and aims to minimize the sum of transportation and unmet demand costs over a planning horizon through bike-transfer strategies under a minimum service requirement. A two-phase heuristic based on linear programming was proposed to solve the problem and produce compromising solutions. In the first phase, the paper developed a linear programming model to quickly develop decisions related to bike inventory, unloading, and loading for all stations for each time slot. In the second phase, this paper proposed an iterative approach through two parameter sensitive mathematical models to sequentially reduce the problem scale to develop decisions related to bike transfers. Computational results show that the proposed approach is superior to a CPLEX optimizer and a hybrid heuristic based on a genetic algorithm. The proposed approach was used to analyze the bicycle system in Taiwan. The impacts of various system parameters on the system were also investigated.     

Optimal size-based opportunistic scheduler for wireless systems

Modern wireless cellular systems are able to utilize the opportunistic scheduling gain originating from the variability in the users’ channel conditions. By favoring users with good instantaneous channel conditions, the service capacity of the system can be increased with the number of users. On the other hand, for service systems with fixed service capacity, the system performance can be optimized by utilizing the size information. Combining the advantages of size-based scheduling with opportunistic scheduling gain has proven to be a challenging task. In this paper, we consider scheduling of data traffic (finite-size elastic flows) in wireless cellular systems. Assuming that the channel conditions for different users are independent and identically distributed, we show how to optimally combine opportunistic and size-based scheduling in the transient setting with all flows available at time 0. More specifically, by utilizing the time scale separation assumption, we develop a recursive algorithm that produces the optimal long-run service rate vectors within the corresponding capacity regions. We also prove that the optimal operating policy applies the SRPT-FM principle, i.e., the shortest flow is served with the highest rate of the optimal rate vector, the second shortest with the second highest rate, etc. Moreover, we determine explicitly how to implement the optimal rate vectors in the actual time slot level opportunistic scheduler. In addition to the transient setting, we explore the dynamic case with randomly arriving flows under illustrative channel scenarios by simulations. Interestingly, the scheduling policy that is optimal for the transient setting can be improved in the dynamic case under high traffic load by applying a rate-based priority scheduler that breaks the ties based on the SRPT principle.     

Modelling complex assemblies as a queueing network for lead time control

In this paper we develop an open queueing network for optimal design of multi-stage assemblies, in which each service station represents a manufacturing or assembly operation. The arrival processes of the individual parts of the product are independent Poisson processes with equal rates. In each service station, there is a server with exponential distribution of processing time, in which the service rate is controllable. The transport times between the service stations are independent random variables with exponential distributions. By applying the longest path analysis in queueing networks, we obtain the distribution function of time spend by a product in the system or the manufacturing lead time. Then, we develop a multi-objective optimal control problem, in which the average lead time, the variance of the lead time and the total operating costs of the system per period are minimized. Finally, we use the goal attainment method to obtain the optimal service rates or the control vector of the problem.     

多类型公共自行车调运问题

公共自行车是我国正大力发展的低碳交通出行模式,加强公共自行车调运优化是提升自行车出行吸引力的关键要素。通过对公共自行车调运背景分析,提出了一类多类型公共自行车的调运优化问题。针对现实生活中租赁站点内公共自行车不均衡的情况,建立了以总成本最小为目标的混合整数线性规划模型,并提出一种改进的混合禁忌搜索对问题进行求解。通过数值实验分析了问题特性并验证了算法性能。实验结果表明非均衡惩罚系数决定了租赁站点各类自行车的装卸载数量,并影响了调配车辆的运行路线,是实现多类型公共自行车均衡优化的关键因素。不同类型自行车的替代策略使得调运决策更加灵活。混合禁忌搜索可以求解更大规模的问题,并能在短时间内求得较好质量的解。     

Robust empty container repositioning considering foldable containers

Because of the extreme imbalance in intercontinental trade, the repositioning of empty containers creates a significant problem for shipping companies. There are many efforts to reduce the cost of repositioning empty containers, one of which is a foldable container. This paper proposes a robust formulation for the empty container repositioning problem considering foldable containers under demand uncertainty. The robust formulation can be used as a tractable approximation of a multistage stochastic programming formulation which is computationally intractable. Moreover, the robust formulation requires only limited information about the distribution of demand to replicate real-world situations. Computational results show that the proposed formulation performs well in terms of operating costs and there exists a significant cost-saving effect when foldable containers are used in maritime transportation.     

A geometric process model for M/M/1 queueing system with a repairable service station

In this paper, we study a geometric process model for M/M/1 queueing system with a repairable service station. By introducing a supplementary variable, some queueing characteristics of the system and reliability indices of the service station are derived. Then a replacement policy N for the service station by which the service station will be replaced following the Nth failure is applied. An optimal replacement policy N¹ for minimizing the long-run average cost per unit time for the service station is then determined.     

Dynamic scheduling to minimize lost sales subject to set-up costs

We consider scheduling a shared server in a two-class, make-to-stock, closed queueing network. We include server switching costs and lost sales costs (equivalently, server starvation penalties) for lost jobs. If the switching costs are zero, the optimal policy has a monotonic threshold type of switching curve provided that the service times are identical. For completely symmetric systems without set-ups, it is optimal to serve the longer queue. Using simple analytical models as approximations, we derive a heuristic scheduling policy. Numerical results demonstrate the effectiveness of our heuristic, which is typically within 10% of optimal. We also develop and test a heuristic policy for a model in which the shared resource is part of a series network under a CONWIP release policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

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

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

Control and scheduling in a two-station queueing network: Optimal policies and heuristics

Consider a two-station queueing network with two types of jobs: type 1 jobs visit station 1 only, while type 2 jobs visit both stations in sequence. Each station has a single server. Arrival and service processes are modeled as counting processes with controllable stochastic intensities. The problem is to control the arrival and service processes, and in particular to schedule the server in station 1 among the two job types, in order to minimize a discounted cost function over an infinite time horizon. Using a stochastic intensity control approach, we establish the optimality of a specific stationary policy, and show that its value function satisfies certain properties, which lead to a switching-curve structure. We further classify the problem into six parametric cases. Based on the structural properties of the stationary policy, we establish the optimality of some simple priority rules for three of the six cases, and develop heuristic policies for the other three cases.     

Optimal control of an M/E<Subscript><Emphasis Type="Italic">k</Emphasis></Subscript>/1 queueing system with removable service station subject to breakdowns

In this paper we deal with a single removable service station queueing system with Poisson arrivals and Erlang distribution service times. The service station can be turned on at arrival epochs or off at departure epochs. While the service station is working, it is subject to breakdowns according to a Poisson process. When the station breaks down, it requires repair at a repair facility, where the repair times follow the negative exponential distribution. Conditions for a stable queueing system, that is steady-state, are provided. The steady-state results are derived and it is shown that the probability that the service station is busy is equal to the traffic intensity. Following the construction of the total expected cost function per unit time, we determine the optimal operating policy at minimum cost.     

Multi-period empty container repositioning with stochastic demand and lost sales

This paper considers repositioning empty containers between multi-ports over multi-periods with stochastic demand and lost sales. The objective is to minimize the total operating cost including container-holding cost, stockout cost, importing cost and exporting cost. First, we formulate the single-port case as an inventory problem over a finite horizon with stochastic import and export of empty containers. The optimal policy for period n is characterized by a pair of critical points (A _n , S _n ), that is, importing empty containers up to A _n when the number of empty containers in the port is fewer than A _n ; exporting empty containers down to S _n when the number of empty containers in the port is more than S _n ; and doing nothing, otherwise. A polynomial-time algorithm is developed to determine the two thresholds, that is, A _n and S _n , for each period. Next, we formulate the multi-port problem and determine a tight lower bound on the cost function. On the basis of the two-threshold optimal policy for a single port, a polynomial-time algorithm is developed to find an approximate repositioning policy for multi-ports. Simulation results show that the proposed approximate repositioning algorithm performs very effectively and efficiently.     

Optimal scheduling policies in time sharing service systems

We consider optimal scheduling problems in a TSSS (Time Sharing Service System), i.e., a tandem queueing network consisting of multiple service stations, all of which are served by a single server. In each station, a customer can receive service time up to the prescribed station dependent upper bound, but he must proceed to the next station in order to receive further service. After the total amount of the received services reaches his service requirement, he departs from the network. The optimal policy for this system minimizes the long-run average expected waiting cost per unit of time over the infinite planning horizon. It is first shown that, if the distribution of customer's service requirement is DMRL (Decreasing Mean Residual Life), the policy of giving the highest priority to the customer with the most attained service time is optimal under a set of some appropriate conditions. This implies that any policy without interruptions and preemptions of services is optimal. If the service requirement is DFR (Decreasing Failure Rate), on the other hand, it is shown that the policy of giving the highest priority to the customer with the least attained service time, i.e., the so-called LAST (Least Attained Service Time first) is optimal under another set of some appropriate conditions. These results can be generalized to the case in which there exist multiple classes of customers, but each class satisfies one of the above sets of conditions.     

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.     

Analysis of multi-server queues with station and server vacations

In this paper, we consider GI/M/c queues with two classes of vacation mechanisms: Station vacation and server vacation. In the first one, all the servers take vacation simultaneously whenever the system becomes empty, and they also return to the system at the same time, i.e., station vacation is a group vacation for all servers. This phenomenon occurs in practice, for example, when the system consists of a set of machines monitored by a single operator, or the system consists of inseparable interconnected parallel machines. In such situations the whole station has to be treated as a single entity for vacation when the system is utilized for a secondary task. For the second class of vacation mechanisms, each server takes its own vacation whenever it complexes a service and finds no customers waiting in the queue, which occurs, for instance in the post office, when each server is a relatively independent working unit, and can itself be used for other purposes. For both models, we derive steady state probabilities that have matrix geometric form, and develop computational algorithms to obtain numerical solutions. We also analyze and make comparisons of these models based on numerical observations.