Asia-Pacific Journal of Operational Research

In the Team Orienteering Problem with Time Windows (TOPTW), a variant of the Vehicle Routing Problem with Profits, a set of locations is given, each associated with a profit, a visiting time and a time window. The aim is to maximize the overall profit collected by a number of routes, while the duration of each route must not exceed a given time budget. TOPTW is NP-hard and is typically used to model the Tourist Trip Design Problem. The latter deals with deriving near optimal multiple-day tours for tourists visiting a destination with several points of interest (POIs). The most efficient known heuristic approach to TOPTW which yields the best solution quality versus execution time, is based on Iterated Local Search (ILS). However, the ILS algorithm treats each node separately, hence it tends to overlook highly profitable areas of nodes situated far from the current solution, considering them too time-expensive to visit. We propose two cluster-based extensions to ILS addressing the aforementioned weakness by grouping nodes on separate clusters (based on geographical criteria), thereby making visits to such nodes more attractive. Our approaches improve ILS with respect to solutions quality and execution time as evidenced by experimental tests exercised on both existing and new TTDP-oriented benchmark instances.

This paper investigates semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the $l_p$-norm of the machines’ loads. We consider two semi-online versions with knowing the total processing time $T$ of all jobs, or knowing the total processing time $T_i$ of the jobs of hierarchy $i$ for $i=1,2$ in advance. For the two semi-online versions, the best possible online algorithms are designed with competitive ratios of ${\phi }^{\ast }$ and $\left(\right.\frac{2^p+4^p}{2{(3)}^p}{\left)\right.}^{\frac{1}{p}}$, respectively, where ${\phi }^{\ast }$ is the maximum value of the function $\phi (x)=\left(\right.\frac{{(x+\frac{1}{2}(1-x))}^p+{(\frac{1}{2}(1-x))}^p}{x^p+{(1-x)}^p}{\left)\right.}^{\frac{1}{p}}$ in $x\in [\frac{1}{2},1]$. When $p=\infty$, our results cover the known results for minimizing the makespan.

This study considers a single-server Markovian working vacation queuing system with Bernoulli vacation interruptions. Based on a linear reward-cost structure, the customer strategic joining behavior is analyzed under different information levels available to the arriving customers, namely fully observable, almost unobservable, and fully unobservable. For these cases, we first obtain the system stationary distribution. Thereafter, we determine the customer equilibrium strategies and compare them numerically with socially optimal strategies.

The paper industry supply chain is highly complex and consists of many processes and planning tasks. It starts with the collection of raw wood and ends up in different paper products from paperboard to high class art papers. Managing the supply chain is difficult and the permanently changing business environment constantly brings new challenges. This paper starts with outlining the challenges in the supply chain management of today’s paper industry. After that we evaluate the state of research to determine planning problems covered by the literature. The purpose is to catch up time-wise on the previous overview from 2009 and also to update the planning problems. This overview paper summarizes comprehensively the paper industry as of today. It provides a reference work for researchers and other interested parties, and uncovers areas for future research.

We use the capacity allocation as a demand management tool to optimize the patient flow distribution on a hierarchical healthcare delivery system, which is a mixture of patient choice and gatekeeping. Capacity allocation for such service system can be challenging because of the inherent stochastic referral process and patients’ heterogeneous delay sensitivities. In this research, a stochastic queueing-based model is proposed to find the optimal allocation of the limited service capacity of the second level of experts. Considering the impact of the deficiency of the skill level and the amount of gatekeepers, the stochastic referral process is modeled with a tandem queue. By solving a fixed-point problem, we show that there is an unique optimal allocation and corresponding equilibrium demand. We carry out numerical studies and find that providing two alternatives for patients can be better than gatekeeper system, when the capacity of the gatekeeper is moderate compared to patients’ potential demand. Results also indicate that the optimal allocation is robust in terms of the referral rate and the mistreatment rate when two rates are less than corresponding thresholds.

For computing the $k$-means clustering of the streaming and distributed big sparse data, we present an algorithm to obtain the sparse coreset for the $k$-means in polynomial time. This algorithm is mainly based on the explicit form of the center of mass and the approximate $k$-means. Because of the existence of the approximation, the coreset of the output inevitably has a factor, which can be controlled to be a very small constant.

It has been found that there is a close relationship between the popularization of electric vehicles and the deployment of the charging facilities, which provides either positive or negative feedback. Given the existence of the double feedback mechanism, namely the indirect network effects, we aim to quantify it by means of empirical research and mathematical modeling. We start with the decision equations, which consist of the consumer’s adoption decision equation and the charging-pile operator’s entrance decision equation. We quantify the influence process by analyzing the equilibrium state and critical equilibrium point. Compared with the general situation in which the scale of the charging piles is decided by the number of electric vehicles, we find that the decision that takes the indirect network effects into consideration has a great positive impact on the popularization of electric vehicles. Our findings shed light on the formulation of incentive policy and the charging-pile operator’s decision-making. We also apply location theory to address the issue of charging-pile points layout in practice.

With the gradual improvement of living standards, people’s consumption levels and habits are changing. One notable fact is that the demand for fresh products is growing steadily. Accordingly, fresh-product preservation and logistics distribution also require higher standards. Based on the practice of fresh domestic transport and preservation, for which the producer and the distributor are responsible, this paper discusses their optimal decisions taking into account the freshness-keeping effort of the distributor. Our main contributions include the derivations of the optimal decisions of the order quantity and the freshness-keeping effort in both the pull and push models, which are common in practice but have not been studied in the literature. Our analytical models lead to the result that, all other settings being the same, the distributor always puts a greater effort into preserving the product quality in the pull model than in the push model. This phenomenon results in a greater distributor’s order quantity and producer’s shipping quantity in the pull model. We also conduct a comprehensive numerical comparison of the effects of different modulating factors, including the price and the proportion and variation of surviving quantity, in these two settings. We find that the profits of the participants and the supply chain are always larger in the pull model, which indicates that the pull model is a better choice for the supply chain.