带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

Rational Abandonment from Tele-Queues: Nonlinear Waiting Costs with Heterogeneous Preferences

We consider the modelling of abandonment from a queueing system by impatient customers. Within the proposed model, customers act rationally to maximise a utility function that weights service utility against expected waiting cost. Customers are heterogeneous, in the sense that their utility function parameters may vary across the customer population. The queue is assumed invisible to waiting customers, who do not obtain any information regarding their standing in the queue during their waiting period. Such circumstances apply, for example, in telephone centers or other remote service facilities, to which we refer as tele-queues. We analyse this decision model within a multi-server queue with impatient customers, and seek to characterise the Nash equilibria of this system. These equilibria may be viewed as stable operating points of the system, and determine the customer abandonment profile along with other system-wide performance measures. We provide conditions for the existence and uniqueness of the equilibrium, and suggest procedures for its computation. We also suggest a notion of an equilibrium based on sub-optimal decisions, the myopic equilibrium, which enjoys favourable analytical properties. Some concrete examples are provided to illustrate the modelling approach and analysis. The present paper supplements previous ones which were restricted to linear waiting costs or homogeneous customer population.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

Controlling the GI/M/1 queue by conditional acceptance of customers

In this paper we consider the problem of controlling the arrival of customers into a GI/M/1 service station. It is known that when the decisions controlling the system are made only at arrival epochs, the optimal acceptance strategy is of a control-limit type, i.e., an arrival is accepted if and only if fewer than n customers are present in the system. The question is whether exercising conditional acceptance can further increase the expected long run average profit of a firm which operates the system. To reveal the relevance of conditional acceptance we consider an extension of the control-limit rule in which the nth customer is conditionally admitted to the queue. This customer may later be rejected if neither service completion nor arrival has occurred within a given time period since the last arrival epoch. We model the system as a semi-Markov decision process, and develop conditions under which such a policy is preferable to the simple control-limit rule.     

基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。     

Modelling and simulation of a supply chain in an uncertain environment

This paper describes fuzzy modelling and simulation of a supply chain (SC) in an uncertain environment, as the first step in developing a decision support system. An SC is viewed as a series of facilities that performs the procurement of raw material, its transformation to intermediate and end-products, and distribution and selling of the end-products to customers. All the facilities in the SC are coupled and interrelated in a way that decisions made at one facility affect the performance of others. SC fuzzy models and a simulator cover operational SC control. The objective is to determine the stock levels and order quantities for each inventory in an SC during a finite time horizon to obtain an acceptable delivery performance at a reasonable total cost for the whole SC. Two sources of uncertainty inherent in the external environment in which the SC operates were identified and modelled: customer demand and external supply of raw material. They were interpreted and represented by fuzzy sets. In addition to the fuzzy SC models, a special SC simulator was developed. The SC simulator provides a dynamic view of the SC and assesses the impact of decisions recommended by the SC fuzzy models on SC performance.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

Optimal dynamic equilibrium in insurance policies

Insurance companies sell contracts of various types each of them having a specific probability of return. Insurers may also own, at the same time, several insurance contracts which evolve through time. In this context, expectation and variance of the free reserves appear as functions of the number of customers in different classes as well as their evolution. Assuming that the customer system can be formulated as an open Markov one characterized by free entry, it is interesting to seek the optimal new customer distribution over the different customer classes j, which permits the minimization of the variance of free reserves for a desired average level of free reserves at a given time horizon. It is shown that, under some conditions, the customer system converges to an optimal growth steady state.     

An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands

We consider the problem of finding the optimal routing of a single vehicle that delivers K different products to N customers according to a particular customer order. The demands of the customers for each product are assumed to be random variables with known distributions. Each product type is stored in its dedicated compartment in the vehicle. Using a suitable dynamic programming algorithm we find the policy that satisfies the demands of the customers with the minimum total expected cost. We also prove that this policy has a specific threshold-type structure. Furthermore, we investigate a corresponding infinite-time horizon problem in which the service of the customers does not stop when the last customer has been serviced but it continues indefinitely with the same customer order. It is assumed that the demands of the customers at different tours have the same distributions. It is shown that the discounted-cost optimal policy and the average-cost optimal policy have the same threshold-type structure as the optimal policy in the original problem. The theoretical results are illustrated by numerical examples.     

Optimizing capacity,pricing and location decisions on a congested network with balking

In this paper, we consider the problem of making simultaneous decisions on the location, service rate (capacity) and the price of providing service for facilities on a network. We assume that the demand for service from each node of the network follows a Poisson process. The demand is assumed to depend on both price and distance. All facilities are assumed to charge the same price and customers wishing to obtain service choose a facility according to a Multinomial Logit function. Upon arrival to a facility, customers may join the system after observing the number of people in the queue. Service time at each facility is assumed to be exponentially distributed. We first present several structural results. Then, we propose an algorithm to obtain the optimal service rate and an approximate optimal price at each facility. We also develop a heuristic algorithm to find the locations of the facilities based on the tabu search method. We demonstrate the efficiency of the algorithms numerically.     

A discrete long-term location–price problem under the assumption of discriminatory pricing: Formulations and parametric analysis

We consider a competitive location problem in which a new firm has to make decisions on the locations of several new facilities as well as on its price setting in order to maximise profit. Under the assumption of discriminatory prices, competing firms set a specific price for each market area. The customers buy one unit of a single homogeneous price-inelastic product from the facility that offers the lowest price in the area the consumers belong to. Three customer choice rules are considered in order to break ties in the offered prices. We prove that, considering long-term competition on price, this problem can be reduced to a problem with decisions on location only. For each one of the choice rules the location problem is formulated as an integer programming model and a parametric analysis of these models is given. To conclude, an application with real data is presented.     

带有回报计划的动态客户关系管理模型及实验应用分析

在客户最大化效用及公司最大化CLV的动态环境下。对所提的带有回报计划的动态客户关系管理模型用于某超市的客户数据库中，发现模型的结果对这类客户是适用的。并给出了不同的客户状态空间对应的有效营销组合策略。结果表明：合适的回报计划可以促进客户的购买、提高公司的利润及缓解价格竞争。回报极限应该比客户的平均购买水平偏高，回报率应该与回报极限的改变方向一致。计划的时间范围应定在一年左右比较合适。对于累积购买水平较高的客户一般不邮寄商品信息。在回报计划的初期与末期不用打折。中期对那些购买次数很少的客户可以实行相应的降价策略。     

线形网络上单台车辆分群调度问题

本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n²) 时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

p-Median theorems for competitive locations

In competitive location theory, one wishes to optimally choose the locations ofr facilities to compete againstp existing facilities for providing service (or goods) to the customers who are at given discrete points (or nodes). One normally assumes that: (a) the level of demand of each customer is fixed (i.e. this demand is not a function of how far a customer is from a facility), and (b) the customer always uses the closest available facility. In this paper we study competitive locations when one or both of the above assumptions have been relaxed. In particular, we show that for each case and under certain assumptions, there exists a set of optimal locations which consists entirely of nodes.This work was supported by a National Science Foundation Grant ECS-8121741.     

Competitive facility location and design problem

We develop a spatial interaction model that seeks to simultaneously optimize location and design decisions for a set of new facilities. The facilities compete for customer demand with pre-existing competitive facilities and with each other. The customer demand is assumed to be elastic, expanding as the utility of the service offered by the facilities increases. Increases in the utility can be achieved by increasing the number of facilities, design improvements, or locating facilities closer to the customer.     

A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.