考虑策略型消费者的在线零售商库存信息披露及联合定价、库存决策模型

在两期销售环境下,研究了面向策略型消费者的在线零售商库存信息披露及联合定价、库存决策问题。考虑在线零售商库存信息共享和隐藏两种库存披露策略,构建了在线零售商两期销售利润模型。通过分析消费者的购买行为,讨论了在具有策略型消费者的市场中,在线零售商应如何选择库存信息披露策略,以及如何制定最优定价和库存决策。在此基础上,分析了相关参数对在线零售商决策及利润的影响。研究结果表明,在线零售商的最优定价及库存决策受消费者估值折扣系数和第二期定价策略的影响。特别地,当在线零售商选择第一期缺货时,更倾向于共享其库存水平信息;当在线零售商选择第二期缺货或者两期均不缺货时,消费者估值折扣系数存在一个阈值,当低于该阈值时,在线零售商会选择隐藏库存水平信息,当高于该阈值时,在线零售商会选择共享库存水平信息。     

信息共享条件下供应链在线与传统销售渠道协调定价

研究了市场需求信息更新条件下,具有传统和在线销售的供应链双源渠道协调问题。建立了以制造商为主方,零售商为从方的Stackelberg主从对策模型,该模型实质是制造商在线销售价格与零售商传统销售价格之间协调;给出了需求信息共享和非共享两种情况下的供应链最优协调价格策略;分析了需求预测信息对供应链最优协调价格策略及其利润的影响;最后进行了数值计算,探讨了需求信息参数对供应链及其成员利润的影响。结果表明,信息共享下的供应链及其成员利润要高于非信息共享情况,而且,越精确的需求预测将导致更高的利润。     

竞争环境下主导电子零售商的销售模式选择和信息共享策略

考虑由单一供应商、单一电子零售商和单一传统零售商组成的供应链，研究了占主导地位的电子零售商的在线销售模式(转售和代理销售)选择及信息共享策略。首先，针对两种在线销售模式，构建了信息共享和不共享情形下以供应链成员利润最大化为目标的优化模型，并通过求解模型得到了供应链成员的均衡定价和订货策略；然后，比较了不同策略组合下供应链各成员的期望利润，分析了各成员的信息共享策略偏好以及电子零售商的销售模式选择策略。研究表明：1)在转售模式下，当市场需求波动程度较小时，信息共享会增加电子零售商的利润，降低供应商和传统零售商的利润；当波动程度较大时，则相反；当市场需求波动处于中等水平时，电子零售商不共享信息能使供应商、电子零售商和传统零售商达成三赢局面。2)在代理销售模式下，信息共享能增加传统零售商的利润，但不一定能增加供应商和电子零售商的利润。只有佣金费率较低，高市场类型的概率较低且市场需求波动不大时，信息共享才是电子零售商的最优策略。3)主导电子零售商应该选择转售模式。本文的研究可为主导电商企业销售模式选择和信息分享决策提供理论依据;为相关零售企业在不同策略组合下定价和订货决策提供支持。     

实时/时变路网环境下城市出救点选择与救援车辆路径的集成动态优化

为了提升城市突发公共事件应急资源调配效率,考虑实时/时变路网环境下出救点选择与救援车辆路径的集成优化问题(CERFSVRP),设计了一种实时/时变交通信息的结合策略,并提出了满足先进先出原则的路段行驶时间计算方法.在此基础上,综合考虑出救点选择、供应能力以及车辆路径连续性等约束条件,以应急响应时间最短为目标,基于虚拟出救点概念和滚动时域策略建立了CERFSVRP动态优化模型.针对该模型的特点,设计了一种改进遗传算法和线性规划法相结合的两阶段算法.算例分析结果表明该模型和算法可以有效解决实时/时变路网环境下城市突发公共事件CERFSVRP动态优化问题.     

滋养你的竞争对手？——考虑电商平台自有品牌的平台需求信息共享策略

针对一个供应商和一个电商平台组成的在线销售系统,在电商平台自有品牌引入决策内生的条件下,研究了平台需求信息共享策略。研究表明：引入自有品牌时,分享需求信息在分销模式下会产生双重边际效应和品牌竞争效应,代销模式下则为收益增加效应和品牌竞争效应。不同销售模式下的需求信息共享策略具有显著差异,当自有品牌引入固定成本过高或者过低时,分销模式下电商平台偏好保留需求信息,代销模式下偏向共享需求信息;当自有品牌引入固定成本中等且产品替代率较大时,电商平台可以通过需求信息共享偏好反转来推动自有品牌的引入。     

供应链中具有产能限制的竞争企业中的信息共享研究

本文研究由一个供货商和两个制造商组成的二级供应链中，制造商之间的横向信息共享策略和供应商的定价问题。在模型中，上游供应商同时为下游两家制造商提供价格相同的原材料，下游制造商生产具有替代性的商品进行数量竞争，并受到相同的产能限制。以Cournot博弈为研究手段，求解了制造商的均衡订货决策和信息共享策略，分析比较了在不同的信息共享策略下制造商的利润、供应商的利润和批发价格。本文在研究制造商的信息共享策略时考虑了上游供应商的批发价格的影响。研究表明，当均衡解受到产能约束时，制造商的信息共享策略会反向。在某些情况下，完全信息共享和完全信息不共享都可能成为博弈的占优策略。上游供应商通过调整批发价格可以影响制造商的信息共享决策。该模型为上游供应商提供了一种最优定价策略，也为下游制造商提供了求解自身最优订货量和信息共享决策的方法。     

存在竞争性制造商的集团采购供应链需求预测信息的共享与激励

针对两个竞争性制造商通过集团采购组织(GPO)采购部件时,是否向GPO共享需求预测信息的激励问题,考虑各制造商拥有有限信息、共享部分信息、基于产量竞争的情形,通过建立博弈模型,分析了竞争强度、信息精度和市场波动对信息共享价值的影响,进而提出了信息共享激励策略。研究表明:信息共享能够协调制造商间的竞争,当且仅当竞争强度超过某阈值时,信息共享能够增加供应链的系统预期利润,此时,用两部制补偿协议可激励制造商完全共享信息;当竞争强度和市场波动均较大时,通过信息共享激励,分散式决策能够实现比集中式决策更大的系统预期利润。最后,通过算例对研究结论进行了直观考察和说明。     

供应链的信息共享机制研究

现在企业间的竞争实际上是供应链的竞争,信息共享是实现供应链管理的基础,关系到供应链的整体效益。本文通过对供应链节点企业缺乏信任而导致信息不共享的问题进行分析,提出供应链信息共享的激励策略和信任合作机制。     

基于策略性竞争博弈的供应链信息共享策略

在供应链成员的市场信息以及成本非对称的情形下,讨论两个终端企业（一个自产自销,一个从上游批发产品）,在供应链中信息共享策略的方案,包括：信息优势企业如何根据市场需求情况确定是否信息共享（若是,则如何共享）;信息劣势企业如何根据对方透露出的市场信息来决策订货量;上游供应链如何决策批发价,从而控制整个供应链的博弈态势,使下游销售商在竞争中更为主动。经过研究发现,低市场类型时,自产自销商乐于共享信息,使竞争对手摄于低迷的市场状况从而降低订货量;在高市场类型且市场波动较小时自产自销商依然选择共享,在乐观的市场条件下表明自己的竞争优势,从而一定程度上威摄入侵者;而市场波动较大时,由于信息共享的额外收益不足以抵消信息共享需付出的额外成本,从而选择不共享信息。     

寡头市场信息产品与服务的最优定价策略

在信息产品与服务竞争性市场中,信息产品及附加服务的定价策略日渐成为信息产品提供商关心的首要问题.而以往的研究多集中于单一信息产品的定价策略,没有统一考虑产品的后续服务,且假设消费者的网络外部性强度相同.分析了异质消费者和双寡头垄断市场,针对基础信息产品和附加服务的定价策略选择问题,建立了双寡头垄断市场中两个企业的捆绑销售和分别销售策略的博弈模型,使得双寡头企业通过4种局势下的策略选择实现收益最大化的定价策略.同时,将差异化网络外部性强度系数引入Hotelling模型,计算企业的需求函数和收益函数,并采用两阶段Bertrand博弈分析两个企业的定价策略和竞争行为.通过模型求解,得到4种局势下两家企业的最优定价解析解.通过数值模拟分析了潜在消费者的构成比例及市场规模对企业定价、市场占有率和最优收益产生的影响,以及不同成本和市场规模组合下企业的最优定价策略.     

The canadian traveller problem and its competitive analysis

From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 ^k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph. We would like to acknowledge the support from NSF of China (No. 70525004, No. 70121001 and No. 60736027), and the support from K.C. Wong Education Foundation, Hong Kong.     

The k-Canadian Travelers Problem with communication

This paper studies a variation of the online k-Canadian Traveler Problem (k-CTP), in which there are multiple travelers who can communicate with each other, to share real-time blockage information of the edges. We study two different communication levels for the problem, complete communication (where all travelers can receive and send blockage information with each other) and limited communication (where only some travelers can both receive and send information while the others can only receive information). The objective is that at least one traveler finds a feasible route from the origin to the destination with as small cost as possible. We give lower bounds on the competitive ratio for both the two communication levels. Considering the urban traffic environment, we propose the Retrace-Alternating strategy and Greedy strategy for both the two communication levels, and prove that increasing the number of travelers with complete communication ability may not always improve the competitive ratio of online strategies.     

On the online multi-agent O–D <Emphasis Type="Italic">k</Emphasis>-Canadian Traveler Problem

In this article, we present new results on the online multi-agent O–D k-Canadian Traveler Problem, in which there are multiple agents and an input graph with a given source node O and a destination node D together with edge costs such that at most k edges are blocked. The blocked edges are not known a priori and are not recoverable. All of the agents are initially located at O. The objective is to find an online strategy such that at least one of the agents finds a route from the initial location O to a given destination D with minimum total cost. We focus on the case where communication among the agents is limited in the sense that some travelers can both send and receive information while the others can only receive information. We formalize the definition of agents’ intelligence by specifying three levels. We introduce two online strategies which utilize higher levels of agents’ intelligence to provide updated lower bounds to this problem. We show that one of our strategies is optimal in both cases with complete and limited communication in the special case of O–D edge-disjoint graphs and highest level of agents’ intelligence.     

The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

In the prize-collecting travelling salesman problem, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow \mathbb {R}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow \mathbb {R}_+\) and the goal is to find a closed tour \(T\) such that \(r\in V(T)\) and such that the cost \(\ell (T)+\pi (V\setminus V(T))\), which is the sum of the edges in the tour and the cost of the vertices not spanned by \(T\), is minimized. We consider an online variant of the prize-collecting travelling salesman problem related to graph exploration. In the Canadian Tour Operator Problem the task is to find a closed route for a tourist bus in a given network \(G=(V,E)\) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node \(v\in V\) by paying a refund of \(\pi (v)\) to the tourists. The goal consists of minimizing the sum of the travel costs and the refunds. We study the problem on a simple (weighted) path and prove tight bounds on the competitiveness of deterministic algorithms. Specifically, we give an algorithm with competitive ratio equal to the golden ratio \(\phi =(1+\sqrt{5})/2\). We also study the effect of resource augmentation, where the online algorithm either pays a discounted cost for traversing edges or for the penalties.     

Faster algorithm to find anti-risk path between two nodes of an undirected graph

For a weighted 2-edge connected graph G=(V,E), we are to find a “minimum risk path” from source s to destination t. This is a shortest s?t path under the assumption that at most one edge on the path may be blocked. The fact that the edge is blocked is known only when we reach a site adjacent to the blocked edge. If n and m are the number of nodes and edges of G, then we show that this problem can be solved in O(n ²) time using only simple data structures. This is an improvement over the previous O(mn+n ²logn) time algorithm. Moreover, with use of more complicated data structures like Fibonacci Heaps and transmuters the time can be further reduced to O(m+nlogn).     

Route vs. Segment: An Experiment on Real‐Time Travel Information in Congestible Networks

We report the results of an experimental study of route choice in congestible networks with a common origin and common destination. In one condition, in each round of play network users independently committed themselves at the origin to a three‐segment route; in the other condition, they chose route segments sequentially at each network junction upon receiving en route information. At the end of each round, players received ex‐post complete information about the distribution of the route choices. Although the complexity of the network defies analysis by common users, traffic patterns in both conditions converged rapidly to the equilibrium solution. We account for the observed results by a Markov adaptive learning model postulating regret minimization and inertia. We find that subjects' learning behavior was similar across conditions, except that they exhibited more inertia in the condition with en route information.     

在线社交网络虚假信息交互量最小化的边阻断策略研究

在线社交媒体的蓬勃发展改变了人们获取信息的模式,大量的信息通过社交平台传播,信息内容的真实性把关弱化,各类虚假信息依托社交媒体野蛮生长,网络空间治理,培育健康的网络生态意义重大。本文通过最小化用户之间的虚假信息交互量,研究社交网络中虚假信息传播路径的阻断策略。给定在线社交网络G=（V,E,P,H）,H表示用户之间信息交互量,已知虚假信息传播源集合S⊆V,虚假信息交互量最小化问题是从E中选取哪K条边,使得这些边被阻断之后,虚假信息在用户之间的交互总量最小。首先证明了该问题是NP-困难的,进而证明了问题的目标函数计算是#P-困难。其次,证明了该问题目标函数既不是次模函数也不是超模函数。再次,提出了两阶段贪婪算法（TSGA）来解决该问题,即先获取候选集合E^sa,然后选取阻断集合E'。最后,通过实际在线社交网络数据对模型和算法的有效性进行了分析,实验表明本文提出的算法比现有算法更加有效。     

Finding an anti-risk path between two nodes in undirected graphs

Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent site of the blocked edge. Let ℘={P _G (s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper will propose the Anti-risk Path Problem of finding a path P _G (s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n ²log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively. This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of China under Grant 20060401003.     

An efficient approach for large scale graph partitioning

In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.     

Constant-Level Greedy Triangulations Approximate the MWT Well

The well-known greedy triangulation GT(S) of a finite point set S is obtained by inserting compatible edges in increasing length order, where an edge is compatible if it does not cross previously inserted ones. Exploiting the concept of so-called light edges, we introduce a definition of GT(S) that does not rely on the length ordering of the edges. Rather, it provides a decomposition of GT(S) into levels, and the number of levels allows us to bound the total edge length of GT(S). In particular, we show |GT(S)| 3 · 2k + 1|MWT(S)|, where k is the number of levels and MWT(S) is the minimum-weight triangulation of S.