Search

With the proliferation of versatile mobile applications, offloading compute-intensive tasks to the MEC/Cloud becomes a dramatic technique due to the limited resources and high user experience requirements at mobile devices. However, most existing works design their task offloading schemes without considering the dependence of tasks and the orchestration of the MEC and Cloud, and thus may limit the system performance. In this paper, we propose a dependent task offloading framework for multiple mobile applications, named COFE, where mobile devices can offload their compute-intensive tasks with dependent constraints to the MEC-Cloud system. It can assign the offloaded tasks to the MEC and Cloud adaptively to improve the user experience. Based on COFE, we formulate the task offloading problem as an average makespan minimization problem, which is proved to be NP-hard. Then, we propose a heuristic ranking-based algorithm to assign the offloaded tasks according to their bottom levels. Theoretical analysis proves the stability of the system under the proposed algorithm and extensive simulations validate that the proposed algorithm can significantly reduce the average makespan and deadline violation probabilities of offloaded applications.

With the rapid development of Internet of Things (IoT) and next-generation communication technologies, resource-constrained mobile devices fail to meet the demand of resource-hungry and compute-intensive applications. To cope with this challenge, with the assistance of Mobile Edge Computing (MEC), offloading complex tasks from mobile devices to edge cloud servers or central cloud servers can reduce the computational burden of devices and improve the efficiency of task processing. However, it is difficult to obtain optimal offloading decisions by conventional heuristic optimization methods, because the decision-making problem is usually NP-hard. In addition, there are shortcomings in using intelligent decision-making methods, e.g., lack of training samples and poor ability of migration under different MEC environments. To this end, we propose a novel offloading algorithm named MR-DRO, consisting of a Meta-Reinforcement Learning (meta-RL) model, which improves the migration ability of the whole model, and a Deep Reinforcement Learning (DRL) model, which combines multiple parallel Deep Neural Networks (DNNs) to learn from historical task offloading scenarios. Simulation results demonstrate that our approach can effectively and efficiently generate near-optimal offloading decisions in IoT environments with edge and cloud collaboration, which further improves the computational performance and has strong portability when making offloading decisions.

Network applications involve massive heterogeneous data fusion and analysis. Artificial intelligence can significantly improve the convenience and user experience, but it requires a lot of storage, bandwidth, and computing resources. Multi-access edge computing (MEC) extends intelligence services to IoT devices through offloading approaches and joint processing, which solves the resource bottleneck. However, designing advanced collaboration technology to offload tasks to MEC servers is still challenging. Heuristic algorithms and deep reinforcement learning (DRL) based approaches have been proposed to offload tasks and minimize application latency. However, heuristic algorithms heavily depend on accurate mathematical models for the MEC system, and DRL does not make fair use of the relationship between devices in the MEC graph. To solve this, we propose a task offloading mechanism based on graph neural network (GNN), which can directly learn on graph data with messages passing and aggregation. We propose a Graph Reinforcement Learning-based Offloading (GRLO) framework, which models MEC as an acyclic graph and the offloading policy by graph state migration. GRLO combines GNN with the actor-critic network and trains offloading decision-makers without labels. To efficiently train the GRLO, we propose a method that quickly explores action space and approaches the optimal solution. The numerical results show that the GRLO has lower latency compared to baselines while having generalization ability to new environments and topologies. Moreover, we verified the effectiveness of GRLO on a prototype.

We consider periodic review perishable inventory systems with a fixed product lifetime. Unsatisfied demand can be either lost or backlogged. The objective is to minimize the long-run average holding, penalty, and outdating cost. The optimal policy for these systems is notoriously complex and computationally intractable because of the curse of dimensionality. Hence, various heuristic replenishment policies are proposed in the literature, including the base-stock policy, which raises the total inventory level to a constant in each review period. Whereas various studies show near-optimal numerical performances of base-stock policies in the classic system with zero replenishment lead time and a first-in-first-out issuance policy, the results on their theoretical performances are very limited. In this paper, we first focus on this classic system and show that a simple base-stock policy is asymptotically optimal when any one of the product lifetime, demand population size, unit penalty cost, and unit outdating cost becomes large; moreover, its optimality gap converges to zero exponentially fast in the first two parameters. We then study two important extensions. For a system under a last-in-first-out or even an arbitrary issuance policy, we prove that a simple base-stock policy is asymptotically optimal with large product lifetime, large unit penalty costs, and large unit outdating costs, and for a backlogging system with positive lead times, we prove that our results continue to hold with large product lifetime, large demand population sizes, and large unit outdating costs. Finally, we provide a numerical study to demonstrate the performances of base-stock policies in these systems. This paper was accepted by Victor Martinez de Albéniz, operations management. Funding: J. Bu was partially supported by a Hong Kong Polytechnic University Start-up Fund for New Recruits [Grant P0039585]. X. Gong was partially supported by a Chinese University of Hong Kong (CUHK) Direct Grant [Grant 4057147] and the Hong Kong Research Grants Council (RGC) General Research Fund [Grant CUHK14500120]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2022.4400 .

Continues field monitoring and searching sensor data remains an imminent element emphasizes the influence of the Internet of Things (IoT). Most of the existing systems are concede spatial coordinates or semantic keywords to retrieve the entail data, which are not comprehensive constraints because of sensor cohesion, unique localization haphazardness. To address this issue, we propose deep learning inspired sensor-rank consolidation (DLi-SRC) system that enables 3-set of algorithms. First, sensor cohesion algorithm based on Lyapunov approach to accelerate sensor stability. Second, sensor unique localization algorithm based on rank-inferior measurement index to avoid redundancy data and data loss. Third, a heuristic directive algorithm to improve entail data search efficiency, which returns appropriate ranked sensor results as per searching specifications. We examined thorough simulations to describe the DLi-SRC effectiveness. The outcomes reveal that our approach has significant performance gain, such as search efficiency, service quality, sensor existence rate enhancement by 91%, and sensor energy gain by 49% than benchmark standard approaches.

Mobile crowd sensing (MCS) is a popular sensing paradigm that leverages the power of massive mobile workers to perform various location-based sensing tasks. To assign workers with suitable tasks, recent research works investigated mobility prediction methods based on probabilistic and statistical models to estimate the worker's moving behavior, based on which the allocation algorithm is designed to match workers with tasks such that workers do not need to deviate from their daily routes and tasks can be completed as many as possible. In this paper, we propose a new multi-task allocation method based on mobility prediction, which differs from the existing works by (1) making use of workers' historical trajectories more comprehensively by using the fuzzy logic system to obtain more accurate mobility prediction and (2) designing a global heuristic searching algorithm to optimize the overall task completion rate based on the mobility prediction result, which jointly considers workers' and tasks' spatiotemporal features. We evaluate the proposed prediction method and task allocation algorithm using two real-world datasets. The experimental results validate the effectiveness of the proposed methods compared against baselines.

Edge computing provides computing capability at close-user proximity to reduce service latency for end users. To improve the efficiency of edge computing infrastructures, geographically-distributed edge datacenters can co-work with each other and with cloud datacenters, forming a new paradigm referred to as cooperative edge-cloud computing. In this context, applications typically run on a virtual machine (VM) that can be replicated at multiple sites, and thus user traffic can be served at all the sites where corresponding VMs reside. For the performance of many applications, latency is a critical parameter. In this work, taking applications latencies as the primary constraint, we model the problem of VM placement and workload assignment as a mixed integer linear program and develop heuristic algorithms accordingly. The goal is to minimize the consumption of information technology (IT) infrastructures for placing VMs in cooperative edge-cloud computing, while meeting the heterogeneous latency demands of different applications. Some preliminary results indicate that edge datacenters resource efficiency can be optimized by proper cross-site VM placement and workload re-direction.

Network function virtualization achieves cost-effective network service provisioning through exploitation of virtualization and automation by decoupling network functions (software) from dedicated hardware. The software of the devices can then be hosted by low-cost computation devices rather than by more expensive dedicated devices. To obtain a specific network service, the traffic flow is steered to go through a specific order of network functions that are hosted by cloud computing, and this network function sequence is known as a service function chaining (SFC). To allocate computation resources for network functions and bandwidth resources between network functions in a physical network is the SFC embedding problem. In this paper, we consider the SFC embedding problem in multi-domain networks, where no domain information, like domain topology and network resource, is disclosed among domains. We propose a new optimization algorithm based on column generation method to solve this problem, which is distributedly computed in domains. To further improve the scalability, we provide two heuristic algorithms. We selected two networks one large (158 nodes) and one small (18 nodes) to numerically validate the proposed algorithms and demonstrate that the acceptance ratio obtained by the heuristic algorithms is close (within 5.6%) to that of the optimal algorithm.

In this paper, we study sensing data collection of IoT devices in a sparse IoT-sensor network, using an energy-constrained Unmanned Aerial Vehicle (UAV), where the sensory data is stored in IoT devices while the IoT devices may or may not be within the transmission range of each other. We formulate two novel data collection problems to fully or partially collect data stored from IoT devices using the UAV, by finding a closed tour for the UAV such that the accumulative volume of data collected within the tour is maximized, subject to the energy capacity on the UAV. To this end, we first propose a novel data collection framework that enables the UAV to collect sensory data from multiple IoT devices simultaneously if the IoT devices are within the coverage range of the UAV. We then formulate two data collection maximization problems to deal with full or partial data collection from sensors and show that both problems are NP-hard. We instead devise approximation and heuristic algorithms for them. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrated that the proposed algorithms are promising.

Mobile Edge Computing (MEC), which is the main technology behind 5th Generation (5G) networks, is a nascent paradigm that meets the demands of IoT (Internet of Things) and localized computing. From an end-user point of view, it can be regarded as a refinement of cloud computing and Fog computing. The transfer of computational tasks to the closet MEC servers leads to energy efficiency and low latency. It is important to apply the most suitable policies for scheduling, especially when configuring different modules of an IoT application in MEC. In this paper, three algorithms, namely the heuristic Bald Eagle Search Optimisation [BESO] algorithm, Particle Swarm Optimization algorithm [PSO], and Genetic Algorithm [GA], are presented to carry out heuristic offloading of computational tasks with a view to improving the latency and performance of MEC. However, the most effective algorithm must be adopted to conduct these tasks. As a result, this paper attempts to find an algorithm that is most appropriate for MEC. To demonstrate this. the three algorithms were tested in the Long-Term Evolution [LTE] based Orthogonal frequency-division multiplexing [OFDM] network during a period when the edge nodes had no adequate resources. The performance and efficiency of the three algorithms, BESO, PSO and GA, were determined and compared. After generating the results, the comparative results were evaluated. In terms of offloading the computational tasks, the BESO algorithm was discovered to perform better, with greater energy efficiency and lower latency, than the other two algorithms.

It is a typical problem in the field of object detection to simultaneously detect objects with large scale variation in one image. Recently proposed state-of-the-art object detectors generally learn pyramidal feature representation to deal with the scale variation, which has been proved effective via various feature pyramid networks. However, the majority of the feature pyramid networks based on heuristic feature fusion strategies may be suboptimal, as excess human guidance will restrict the self-learning of deep neural networks. An adaptive feature pyramid is bound to provide a significant performance boost. In this paper, we propose a novel feature pyramid network named CATFPN that consists of Scale-Wise Feature Concatenation (SWFC) module and Global Context (GC) block. The SWFC module evenly distributes semantic features for each feature layer and the GC block introduces a self-attention mechanism. As a feature pyramid network, the CATFPN can be applied to any detector based on multi-scale features. We adopt the CATFPN in typical RetinaNet and Faster R-CNN detector models, without bells and whistles, achieving 1.1% AP and 0.7% AP improvements over FPN on the MS COCO benchmark, respectively. Our competitive performance reported on the test-dev subset of COCO achieves 42.3% AP.

The multipoint dynamic aggregation (MPDA) problem of the multirobot system is of great significance for its real-world applications such as bush fire elimination. The problem is to design the optimal plan for a set of heterogeneous robots to complete some geographically distributed tasks collaboratively. In this article, we consider the dynamic version of the problem, where new tasks keep appearing after the robots are dispatched from the depot. The dynamic MPDA problem is a complicated optimization problem due to several characteristics, such as the collaboration of robots, the accumulative task demand, the relationships among robots and tasks, and the unpredictable task arrivals. In this article, a new model of the problem considering these characteristics is proposed. To solve the problem, we develop a new genetic programming hyperheuristic (GPHH) method to evolve reactive coordination strategies (RCSs), which can guide the robots to make decisions in real time. The proposed GPHH method contains a newly designed effective RCS heuristic template to generate the execution plan for the robots according to a GP tree. A new terminal set of features related to both robots and tasks and a cluster filter that assigns the robots to urgent tasks are designed. The experimental results show that the proposed GPHH significantly outperformed the state-of-the-art methods. Through further analysis, useful insights such as how to distribute and coordinate robots to execute different types of tasks are discovered.

In this paper, we study a novel service reliability augmentation problem in an Edge Computing network, where mobile users request network services with a service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant network function (VNF) instance placement in case their primary VNF instances fail. To this end, we first formulate a novel service reliability augmentation problem for each admitted request and show the NP-hardness of the problem. We then provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets, and then develop a randomized algorithm with a good approximation ratio and high probability for the service reliability augmentation problem, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We thirdly extend the proposed algorithm for a single request to the service reliability augmentation problem for a set of requests. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and superior to their analytical counterparts.

Low-rank plus sparse matrix decomposition (LSD) is an important problem in computer vision and machine learning. It has been solved using convex relaxations of the matrix rank and l0-pseudo-norm, which are the nuclear norm and l1-norm, respectively. Convex approximations are known to result in biased estimates, to overcome which, nonconvex regularizers such as weighted nuclear-norm minimization and weighted Schatten p-norm minimization have been proposed. However, works employing these regularizers have used heuristic weight-selection strategies. We propose weighted minimax-concave penalty (WMCP) as the nonconvex regularizer and show that it admits an equivalent representation that enables weight adaptation. Similarly, an equivalent representation to the weighted matrix gamma norm (WMGN) enables weight adaptation for the low-rank part. The optimization algorithms are based on the alternating direction method of multipliers technique. We show that the optimization frameworks relying on the two penalties, WMCP and WMGN, coupled with a novel iterative weight update strategy, result in accurate low-rank plus sparse matrix decomposition. The algorithms are also shown to satisfy descent properties and convergence guarantees. On the applications front, we consider the problem of foreground-background separation in video sequences. Simulation experiments and validations on standard datasets, namely, I2R, CDnet 2012, and BMC 2012 show that the proposed techniques outperform the benchmark techniques.

In this work, we study an important task in location-based services, namely Personalized Route Recommendation (PRR). Given a road network, the PRR task aims to generate user-specific route suggestions for replying to users' route queries. A classic approach is to adapting search algorithms to construct pathfinding-like solutions. These methods typically focus on reducing search space with suitable heuristic strategies. For these search algorithms, heuristic strategies are often handcrafted, which are not flexible to work in complicated task settings. In this paper, we propose to improve search algorithms with neural networks for solving the PRR task based on the widely used A* algorithm. Our model consists of two components. First, we employ attention-based Recurrent Neural Networks (RNN) to model the cost from the source to the candidate location by incorporating useful context information. Second, we propose to use an estimation network for predicting the cost from a candidate location to the destination. The two components are integrated in a principled way for deriving a more accurate cost of a candidate location for the A* algorithm. Extensive experiment results on three real-world datasets have shown the effectiveness and robustness of the proposed model.

The software systems with a well-documented architecture are easy to understand and evolve. However, in most cases, either the documented architecture is unavailable or get eroded badly. In these cases, to understand and evolve the software systems, developers often need to recover the architectural components from the system implementation code. Recently, a variety of heuristic-based multi-objective optimization algorithms (MoOAs) for software architecture recovery (SAR) have been introduced. Most of the existing SAR approaches are designed by adopting the traditional MoOAs. However, the performance of such approaches degrades drastically with large-scale many-objective SAR (LSMaO-SAR). To address the challenges the MoOAs caused by the LSMaO-SAR, we introduce a large-scale many-objective particle swarm optimization (LSM-PSO) by customizing the framework of the PSO algorithm. For this, we adopt various strategies such as Balance Fitness Evaluation (BFE), Quality Indicator (QI) based fitness evaluation, Fuzzy-Pareto dominance (FPD), and Two-archive external storage, and incorporate into the PSO model. To test the effectiveness of the LSM-PSO, it is applied over five software projects and compared with the existing SAR approaches. The results show that the proposed LSM-PSO outperforms the existing optimization-based SAR approaches.

Problem Definition: Problem Definition: We develop a framework to plan capacity for ambulatory surgery centers (ASCs) typically consisting of three stages. The problem is to determine the capacity in each stage that efficiently covers possible daily patient demand and to coordinate the three stages of patient visits. The objective is to minimize the total cost incurred in satisfying the daily patient demand, where the total cost is defined as the sum of overtime cost and amortized construction cost for the three stages. Academic/Practical Relevance: Timely capacity adjustment is important for ASC practitioners, but related research is limited. We explicitly consider three sequential stages that are typical in ASCs: the pre-operative at holding room (HR), intra-operative at operating room (OR), and post-operative at post-anesthesia care unit (PACU). Such ASCs can be modeled as a hybrid flow shop (HFS) in the scheduling literature. The interdependence of activities and uncertainties in patient-mix as well as their durations pose a significant challenge to manage the capacity of each activity and achieving a smooth patient flow. Methodology: In contrast to the traditional top-down approach to capacity planning, our approach contributes by proposing a bottom-up strategy based on optimization methods combined with analytics that are informed by operational-level archival patient data. Specifically, we use analytics tools to classify patients into groups, which reduces the complexity of the capacity planning problem and improves the model's practicality. Later, we develop several mathematical formulations and heuristics based on scheduling theory to derive the most cost-efficient capacity solution. Results: Given the trade-off between overtime cost and amortized capacity construction cost, this study relaxes the fixed capacity assumption of traditional HFS problems. Because of the computational complexity of the exact HFS model, we develop a heuristic that is straightforward and easy to implement to find cost-efficient capacities for the three stages. Our computational study examines how uncertain business parameters, e.g., patient-mix, service durations, overnight-stay probabilities, affect the capacity planning decision. Managerial implications: This study highlights the benefit of considering multiple stages together in capacity planning, rather than focusing solely on the operating rooms exclusively. We expect our approach to guide the more than 5,000 ASCs in the U.S., performing 23 million surgeries annually, to make appropriate investments that will improve ASC operations via capacity adjustment and patient scheduling.

Recent technological breakthroughs have allowed unmanned aerial vehicles (UAVs) to be utilized in a broad range of new operations. Among these various applications, herein, we focus on the use of UAVs for search and rescue missions in emergency and postdisaster scenarios. In this context, self-charging technologies for drones create new challenges in the routing of UAVs with charging stations. We present a variant of the vehicle routing problem (VRP) to address the integrated use of UAVs and mobile charging stations and define the VRP with synchronized networks (VRPSN), a new class of VRPs involving the routing of UAVs whose recharge platforms can travel to different locations during an operation. This leads to two networks within the VRP that must be integrated and synchronized. This research develops a mixed-integer linear program model for the VRPSN that considers the use of UAVs and mobile charging stations in a synchronized manner. To overcome the computational limits of the MILP model, this research presents a construct-and-adjust heuristic method integrated with a genetic algorithm. As a numerical example, we test the proposed model on the Corrego do Feijao Mine located in Minas Gerais, Brazil, where a dam recently collapsed, killing many workers. Numerical tests show that the new methodology is an attractive planning method for providing efficient and rapid responses in search and rescue missions.

Bug triaging is a critical and time-consuming activity of software maintenance. This paper aims to present an automated heuristic approach combined with fuzzy multi-criteria decision-making for bug triaging. To date, studies lack consideration of multi-criteria inputs to gather decisive and explicit knowledge of bug reports. The proposed approach builds a bug priority queue using the multi-criteria fuzzy Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) method and combines it with Bacterial Foraging Optimization Algorithm (BFOA) and Bar Systems (BAR) optimization to select developers. A relative threshold value is computed and categorization of developers is performed using hybrid optimization techniques to make a distinction between active, inactive, or new developers for bug allocation. The harmonic mean of precision, recall, f-measure, and accuracy obtained is 92.05%, 89.21%, 85.09%, and 93.11% respectively. This indicates increased overall accuracy of 90%±2% when compared with existing approaches. Overall, it is a novel solution to improve the bug assignment process which utilizes intuitive judgment of triagers using fuzzy multi-criteria decision making and is capable of making a distinction between active, inactive, and new developers based on their relative workload categorization.

Robot path planning in 3D space is a challenging problem for its complex configuration. Sampling-based algorithms have gained great success in solving path planning problems in 3D space, but the quality of the initial path is not guaranteed and the convergence to the optimal solution is slow. To address these problems, in this article, we present a novel sampling-based path planning framework enhanced by the deep neural network (DNN) with applications to 3D space. In the proposed framework, we first train the DNN with a number of successful path planning cases in 3D space. Then the DNN is utilized to predict the promising region where the feasible path probably exists for a given path planning problem. This predicted promising region serves as a nonuniform sampling heuristic to bias the sampling process of the path planner. In this way, the path planner can focus on the promising region in the exploration and exploitation process so that the path planning speed gets accelerated. We conduct numerical simulations to evaluate the performance of the proposed algorithm and the results show that it can perform much better than conventional path planning algorithms. Furthermore, we also investigate the performance of different DNN architectures for path planning in 3D space.

With the surging energy cost and environmental impacts, strategies to achieve energy-efficient production have attracted increasing concerns of the manufacturing enterprises. For the fact that most manufacturing systems operate in a dynamic and nondeterministic environment, rescheduling strategies may be beneficial as it serves for adaption of initial schedule to dynamic events. Besides that, the development of modern information technology in manufacturing practice enables the flexibility of production toward alternative process plans. However, very little research has focused on the rescheduling problem integrated with process planning for energy saving. Hence, this work undertakes this challenge by proposing rescheduling decision mechanisms in response to two typical dynamic events with alternative process plans for energy-efficient flexible job shops. More specifically, by modeling the energy consumption of the flexible manufacturing system, the problem is first formulated as a mixed-integer programming optimization model. Rescheduling mechanisms for both new job arrivals and machine tool breakdowns are then designed, based on which a rescheduling algorithm is proposed in the form of a heuristic framework. The significance of the proposed algorithm is exemplified by a comparative case study under various scenarios.

The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max-min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.

This paper proposes a primary and backup resource allocation model that provides a probabilistic protection guarantee for virtual machines against multiple failures of physical machines in a cloud provider to minimize the required total capacity. A physical machine allocates both primary and backup computing resources for virtual machines. When any failure occurs, the survived physical machines with preplanned backup resources recover the virtual machines on the failed physical machines and take over the workloads. The probability that the protection provided by a physical machine does not succeed is guaranteed within a given number. Providing the probabilistic protection can reduce the required backup capacity by allowing backup resource sharing, but it leads to a nonlinear programing problem in a general-capacity case against multiple failures. We apply robust optimization with extensive mathematical operations to formulate the primary and backup resource allocation problem as a mixed integer linear programming problem, where capacity fragmentation is suppressed. We prove the NP-hardness of considered problem. A heuristic is introduced to solve the optimization problem. The results reveal that the proposed model saves about one-third of the total capacity in our examined cases; it outperforms the conventional models in terms of both blocking probability and resource utilization.

Large-scale graphs are widely used to model the entities and their complex relations. Uncertain graphs are adopted when the relations between entities contain some uncertainty. However, the inherent uncertainties, which are embedded underlying the data and structure of the graphs derived from various sources introduce difficulties on data analysis. To understand the underlying characteristics of large graphs, graph aggregation techniques are critical. However, the existing graph aggregation techniques are designed for deterministic graphs therefore are not applicable on uncertain graphs. In this paper, we provide the first attempt on addressing the aggregation problem on uncertain graphs. To deal with the computation complexity of the aggregation problem, we propose a heuristic-based aggregation algorithm for uncertain graphs and some optimization methods to improve its efficiency in real world implementation. Besides the optimization, to further speed up the process, we design a parallel aggregation implementation approach. The intensive evaluations on the two datasets, DBLP and Flickr, demonstrate that our proposed algorithms are able to produce high quality aggregation results within reasonable operation time and the parallel implementation accelerates the aggregation by up to 82 times compared with the baseline algorithm.

To solve the autonomous navigation problem in complex environments, an efficient motion planning approach called EffMoP is presented in this paper. Considering the challenges from large-scale, partially unknown complex environments, a three-layer motion planning framework is elaborately designed, including global path planning, local path optimization, and time-optimal velocity planning. Compared with existing approaches, the novelty of this work is twofold: 1) a heuristic-guided pruning strategy of motion primitives is newly designed and fully integrated into the search-based global path planner to improve the computational efficiency of graph search, and 2) a novel soft-constrained local path optimization approach is proposed, wherein the sparse-banded system structure of the underlying optimization problem is fully exploited to efficiently solve the problem. We validate the safety, smoothness, flexibility, and efficiency of EffMoP in various complex simulation scenarios and challenging real-world tasks. It is shown that the computational efficiency is improved by 66.21% in the global planning stage and the motion efficiency of the robot is improved by 22.87% compared with the recent quintic Bezier curve-based state space sampling approach.

In the present scenario sustainable management and protection of digital cultural datasets are considered as a significant area of research. In the recent past, the protection and management of cultural data are facing several new challenges and opportunities. Though several researchers explored their work on managing and protecting cultural data, efficiently and reliability of the present data management algorithm seems to be more complicated due to its incompetence in managing data in an optimized manner. This work presents an improved heuristic big data management algorithm for cultural datasets which is considered as a new discipline of digital cultural heritage specially established for strengthening strategic and interdisciplinary research. The scientific operation and management mechanism of digital protection of cultural heritage is experimentally validated and results show promising outcomes.

Various crowdsourced logistics platforms are forming rapidly along with the booming mobile Internet. Motivated by modern crowdsourced truck logistics platforms, we introduce the online crowdsourced truck delivery (OCTD) problem and reformulate it as the online bipartite hyper-matching problem. We then explore the possibility of accommodating historical information to design efficient online algorithms to serve online orders. To the best of our knowledge, it is the first work on incorporating historical information to solve the online bipartite hyper-matching problem. Depending on whether orders can be partially served, we investigate two practical situations, i.e. separable and inseparable cases. For the inseparable case, we propose a randomized online algorithm, named Hyper-Matching , whose competitive ratio is a non-decreasing function of the amount of historical information. For the separable case, we modify Hyper-Matching to present another randomized online algorithm, named Separable-Hyper-Matching . It is worth noting that the competitive ratios of Hyper-Matching and Separable-Hyper-Matching either beat or match the current best online algorithms when no historical information is considered. We then present four computationally efficient heuristic algorithms, including a greedy variant and a batch-processing variant for each of the inseparable and separable cases. We perform a sequence of experiments using synthetic and real-world datasets, with an emphasis on the influence that historical information has on algorithm performance. The experiment results demonstrate the effectiveness of our algorithms and particularly the positive influence of historical information on our algorithms.

Task scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm can potentially increase the efficiency of cloud computing, by choosing the appropriate virtual machine to do a specific task-scheduling problem, for dependent tasks on heterogeneous resources which is a well-known NP-Hard problem. To reduce minimum total execution time, makespan, in cloud computing many heuristics were presented in literature but lots of them suffer from low efficiency. In this article, a new task priority strategy and applying task duplication methods are proposed, for solving the task scheduling problem of the dependent tasks in heterogeneous cloud computing systems. The novelty of the current paper is to present a new list scheduling algorithm with a new task priority strategy and applying pertinent task duplication techniques. This paper uses optimistic cost table downward (OCTd) and optimistic cost table upward (OCTu) procedures to prioritize tasks in an efficient ordered list; then, it utilizes Heterogeneous Earliest Finish Time (HEFT)-duplication method for performing task duplication technique which significantly reduces makespan. To validate the proposal, we experimentally analyzed the proposed scheduling algorithm with different scientific workflows such as Molecular, LU-Like, FFT, and Montage datasets. The performance comparison of the novel heuristic scheduling algorithm against other existing approaches proved the superiority of proposed algorithm in terms of makespan, speedup, SLR, and efficiency which are prominent scheduling evaluation metrics.

Transcoding in video live-streaming systems requires a lot of computation and, hence, a lot of power. Putting a limit on the power drawn by each of the transcoding processors in a server reduces the overall power consumption, but it also hinders the efficient allocation of transcoding tasks. We address this with a dynamic programming algorithm, together with a heuristic, which maximizes total processing capacity while limiting power consumption in a server with heterogeneous processors. A further greedy algorithm determines the bitrates, at which content is transcoded for each channel, and allocates transcoding tasks to processors, while taking video quality, popularity, and workload balance into account. The initial assumption is that all contents are transcoded to all bitrates for every channel. Then, the algorithm gradually reduces the number of versions to be produced by transcoding, while minimizing the consequent reduction in popularity-weighted video quality, as well as balancing the workload across processors. Experimental results show that our scheme improves aggregate popularity-weighted video quality under a power constraint by 3.82%–39.12%, compared to benchmark methods.

Reorganizing bus frequencies to cater for actual travel demands can signicantly save the cost of the public transport system. This paper studies the bus frequency optimization problem considering the user satisfaction. Specically, for the rst time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efciently, we rst present an index-based (1 1/e)-approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method for that achieves a (1)(1 1/e) approximation ratio. Then we propose a progressive partition-based greedy method for to further boost the efciency while achieving a (1)(1 1/e) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efciency, effectiveness, and scalability of our methods in addressing FAST and FASTCO.

Todays large-scale parallel workflows are often processed on heterogeneous distributed computing platforms. From an economic perspective, computing resource providers should minimize the cost while offering high service quality. It has become well-organized that energy consumption accounts for a large part of a computing systems total cost, and timeliness and reliability are two important service indicators. This article studies the problem of scheduling a parallel workflow that minimizes the system energy consumption under the constraints of response time and reliability. We first mathematically formulate this problem as a Non-linear Mixed Integer Programming problem. Since this problem is hard to solve directly, we present some highly-efficient heuristic solutions. Specifically, we first develop an algorithm that minimizes the schedule length while meeting reliability requirement, on top of which we propose a processor-merging algorithm and a slack time reclamation algorithm using a dynamic voltage frequency scaling (DVFS) technique to reduce energy consumption. The processor-merging algorithm tries to turn off some energy-inefficient processors such that energy consumption can be minimized. The DVFS technique is applied to scale down the processor frequency at both processor and task levels to reduce energy consumption. Experimental results on two real-life workflows and extensive synthetic parallel workflows demonstrate their effectiveness.

Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.

We consider the design of a robust procurement mechanism for an assembler who must procure multiple complementary components under limited information regarding the unit production costs of the potential suppliers. We abandon the standard assumption that there exists a common prior distribution for the suppliers’ costs and we employ the max-min criterion in which we design a mechanism to maximize the assembler’s worst-case expected profit when only the means of the suppliers’ costs are known. We formulate this problem using a linear semi-infinite programming model and we apply a primal-dual approach to reduce the problem to a single joint optimization model. We characterize the optimal procurement mechanism (payments and ordering quantities) under the assumption of balanced ordering and uncertain end-customer demand. We use these results to compare the performance of component production, under which the components are sourced from separate suppliers, and integrated production, under which the components are sourced from the same supplier. We find that component production is preferred when the production costs of the components are heterogeneous. We also propose two heuristic mechanisms which are easier to compute and implement in practice, particularly when the number of components is large. Finally, we extend our analysis to the case in which the average and variance of the suppliers’ costs are known.

A colored traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k -exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.

The net orders in detailed routing are crucial to routing closure, especially in most modern routers following the sequential routing manner with the rip-up and reroute scheme. In advanced technology nodes, detailed routing has to deal with complicated design rules and large problem sizes, making its performance more sensitive to the order of nets to be routed. In literature, the net orders are mostly determined by simple heuristic rules tuned for specific benchmarks. In this work, we propose an asynchronous reinforcement learning (RL) framework to automatically search for optimal ordering strategies and a transfer learning (TL) algorithm to improve performance. By asynchronous querying, the router, pre-training the RL agents, and finetuning with the TL algorithm, we can generate high-performance routing sequences to achieve a 26% reduction in the DRC violations and a 1.2% reduction in the total costs compared with the state-of-the-art detailed router.

Nowadays, increasing business applications running in the cloud are embracing the microservice architecture. This paper presents the challenges and implications of diagnosing root causes of anomalies in large-scale microservice architecture using real incidents in IBM Bluemix. We propose ServiceRank, a novel framework for anomaly detection and root cause identification in the microservice architecture to tackle these challenges. ServiceRank introduces an anomaly detector followed by a root cause analysis module, which detects the suspected abnormal service without pre-defined thresholds. To generalize our approach, we design a dynamic causal relationship extraction approach to construct impact graphs for root cause investigation according to specific anomalies. To eliminate cloud design-patterns' impact on anomaly diagnosis, we propose a mechanism called correlation calibration in ServiceRank and present a calibration algorithm for the circuit breaker - a typical protection pattern in the microservice architecture. Finally, we design a heuristic investigation algorithm based on the second-order random walk to identify the anomaly's root cause. Experimental results in a simulated environment and the IBM Bluemix platform show that ServiceRank outperforms selected approaches in accuracy and offers fast identification of root cause service when an anomaly occurs. Moreover, we can deploy ServiceRank rapidly and easily in various systems without any pre-defined knowledge.

The tuning of Microwave Cavity Filters (MCFs) is mostly conducted by experienced operators, and thus is time and resource intensive. The automatic tuning method has received lots of research attention. However, the experience of tuning experts is not described systematically, and the existing methods are not adequate for MCFs with individual differences. Considering that fuzzy expert systems are superior in flexibility and interpretability, a dynamic attention based heuristic fuzzy expert system is proposed in this paper to achieve automatic tuning with high applicability, accuracy, and efficiency. First, the dynamic tuning process is divided into several stages, and the evaluation function of filtering performance is designed for each stage. Second, an improved expert system with dynamic attention is constructed to facilitate the comprehensive evaluation of filtering performance and to balance tuning efficiency and accuracy. Third, a heuristic fuzzy logic system is presented to obtain appropriate tuning values, with low design complexity of fuzzy rules and high utilization of tuning process information. Last, the effectiveness, applicability, and practicality of the proposed method are demonstrated by both simulations and experiments.

A flow-shop production environment is a widely used production setting in the industry, especially preferred when the variety of products and processes is limited. The constant development of technology and the increasing competition in the market compel researchers to seek ways to increase efficiency. Therefore, scheduling remains an important area of study for researchers. When the size of the problem increases, particularly in real-life contexts, it becomes almost impossible to work out a feasible solution to scheduling problems through current computer technologies. In such cases, solutions are often developed using heuristic or meta-heuristic methods. However, the performance of these methods may vary according to the problem or the components of the suggested method of solution. This study aimed to investigate the effect of local search strategies on the solution performance of hybrid firefly and particle swarm optimization algorithm, developed using chaotic local search. We used four different solution methods: the triple local search strategy consisting of insertion, swap and inversion, which were used frequently in earlier studies, and the individual use of each of these three strategies. In this study, the average relative difference values calculated using insertion, swap, inversion and triple strategy were found to be 3.03, 1.27, 2.54 and 1.20, respectively. As a result of the analyses carried out to compare the results of the solutions obtained in the flow-shop scheduling problems of Taillard, it was found that better results were obtained using the triple strategy. These findings can be a point of reference for future research.

This paper presents a collaboratively adaptive vibration monitoring system that captures high-fidelity structural vibration signals induced by pedestrians. These signals can be used for various human activities’ monitoring by inferring information about the impact sources, such as pedestrian footsteps, door opening and closing, and dragging objects. Such applications often require high-fidelity (high resolution and low distortion) signals. Traditionally, expensive high resolution and high dynamic range sensors are adopted to ensure sufficient resolution. However, for sensing systems that use low-cost sensing devices, the resolution and dynamic range are often limited; hence this type of sensing methods is not well explored ubiquitously. We propose a low-cost sensing system that utilizes (1) a heuristic model of the investigating excitations and (2) shared information through networked devices to adapt hardware configurations and obtain high-fidelity structural vibration signals. To further explain the system, we use indoor pedestrian footstep sensing through ambient structural vibration as an example to demonstrate the system performance. We evaluate the application with three metrics that measure the signal quality from different aspects: the sufficient resolution rate to present signal resolution improvement without clipping, the clipping rate to measure the distortion of the footstep signal, and the signal magnitude to quantify the detailed resolution of the detected footstep signal. In experiments conducted in a school building, our system demonstrated up to 2× increase on the sufficient resolution rate and 2× less error rate when used to locate the pedestrians as they walk along the hallway, compared to a fixed sensing setting.

The quality of covert communications is determined by the choice of communication channels and the design of data embedding schemes. Recently, the Bitcoin system is prevalent as a covert communication channel. The consensus mechanism requires participants to spread their found valid blocks under an adjustable difficulty, which provides a stable periodic broadcast channel. Moreover, senders and receivers are difficult to be traced, because the Bitcoin system is pseudonymous. However, since the historical data in the ledger cannot be removed from the Bitcoin system, the openness and the persistent storage of the ledger in the Bitcoin system post new challenges when designing data embedding schemes. More concreteness, most traditional data embedding schemes either design by heuristic or empirical algorithms or use a fixed field to embed data in the transactions. Therefore, the covert data can be recognized once the algorithm is leaked or the pattern is explored. In this article, we first propose a Hash Chain-based Covert Data Embedding (HC-CDE) Scheme. The embedded transactions are difficult to be discovered. We further propose an Elliptic Curve Diffie-Hellman Chain-based Covert Data Embedding (ECDHC-CDE) Scheme to enhance the security of the HC-CDE scheme. Experimental analysis on the Bitcoin Testnet verifies the security and the efficiency of the proposed schemes.

Uncertain data has been emerged as an important problem in database systems due to the imprecise nature of many applications. To handle the uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the uncertainty may propagate, hence the results from a query or mining process may not be useful. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks (HITs) to ask a crowd with diverse accuracy rates, to improve the quality of uncertain data. Each HIT is associated with a cost, thus, we need to design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, even under diverse individual accuracy rates of the crowdsourcing workers.

The rake movements in rail freight transportation are executed by dynamically allocating empty rakes to observed demands. This work proposes an alternate cycle planning strategy based on the average demand data. The system is modeled as the Pickup and Delivery Problem with customer specified origin and destination and multiple full truckload demands by each customer. Initially, an Exact Formulation of the problem that gives optimal cycles is presented. A modified Order First Split Second Heuristic (OFSS) is proposed to solve the deterministic version of this problem where a giant tour is constructed by assigning a value to each node based on the greedy path from that location. The splitting algorithm forms multiple cycles satisfying maximum cycle time constraint from the Giant Tour. A heuristic solution obtained by splitting optimal giant tour is also determined to study the performance of proposed heuristic. Considering the possibility of deviation of actual demands from average, an adaptive algorithm that modifies the planned cycles to accommodate the changes in demand is presented. Computations show that the heuristic gives near-optimal solution in terms of net revenue and the number of vehicles required. Testing this algorithm on dynamic demands show that the initial cycle plan can be followed with minor modification if the Degree of Dynamism of the system is small. The proposed algorithm is tested on Indian freight rail data and the improvements in rake utilization are noted.

Fully automated vehicles deployed with high computational/perceptive capabilities will soon become a reality. Such capabilities enable the cooperation among vehicles and the realization of interacting autonomous driving systems. Edge computing has emerged to provide a plethora of computational services to reduce network latency. Applications at the edge that apply analytics on the sensory data are therefore indispensable for self-driving vehicles. We consider in this paper a network that interconnects vehicles to an edge server at a roadside unit. Each vehicle extracts multiple information by sampling multiple processes and sends them to the corresponding edge application. To make timely decisions, ``fresh'' information needs to be offloaded, processed, and delivered back to vehicles; in this context, we adopt a new metric called Age of Information (AoI) that has been lately used to measure the freshness of information. We seek to jointly schedule vehicles' transmission of information and schedule information processing at the edge to minimize the AoI of all processes. We mathematically formulate the problem and prove its NP-Hardness. To overcome this hardness, we propose a logic-based Benders decomposition to divide the problem into a master and several subproblems. Then, we present an exact polynomial-time solution for the subproblems, a scalable heuristic for the master, and devise a valid yet efficient Benders cut. We implement the system simulation on the well-known traffic simulator SUMO and compare the decomposition with CPLEX branch-and-cut; Although the problem is highly intricate, our method finds a near-optimal solution (maximum deviation is 7% from optimal solution) with a speedup that reaches 95%. We study the system performance by varying different system parameters.

Scheduling the recharging of electric vehicle fleets under different scenarios is an important but open problem. One important scenario is that vehicles travel at different speeds in different periods since traffic congestion is common in urban areas nowadays. Therefore, in this article, a novel time-dependent electric vehicle routing problem with congestion tolls is proposed. If a vehicle enters a peak period, a fixed congestion toll needs to be paid in this problem. A mixed integer linear programming model is established and an adaptive large neighborhood search (ALNS) heuristic is designed to solve the model. The model and solving method are validated and evaluated extensively with benchmark instances. Results indicate that a certain level of congestion tolls could prevent vehicles from entering peak periods and relieve road congestions significantly. Furthermore, the ALNS heuristic could provide much better solutions for the problem than typical optimization software, such as Gurobi, in much shorter running time.

In this paper, we investigate the dynamic task scheduling problem with stochastic task arrival times and due dates in the UAV-based intelligent on-demand meal delivery system (UIOMDS) to improve the efficiency. The objective is to minimize the total tardiness. The new constraints and characteristics introduced by UAVs in the problem model are fully studied. An iterated heuristic framework SES (Stochastic Event Scheduling) is proposed to periodically schedule tasks, which consists of a task collection and a dynamic task scheduling phases. Two task collection strategies are introduced and three Roulette-based flight dispatching approaches are employed. A simulated annealing based local search method is integrated to optimize the solutions. The experimental results show that the proposed algorithm is robust and more effective compared with other two existing algorithms.

Nowadays the majority of retail customers use multiple channels. We investigate the assortment, space and inventory problem for an omni-channel retailer operating with interconnected bricks-and-mortar stores and an online shop. For this problem it becomes essential to consider customers’ demand interactions across channels. Current literature mainly focuses on single-channel assortments and ignores cross-channel substitution. We contribute the first integrated omni-channel model that determines assortments for the online and bricks-and-mortar channel with stochastic, space-elastic and out-of-assortment and out-of-stock demand both for in-channel substitution and cross-channel substitution. A specialized heuristic is developed that is based on an iterative solution of a binary problem and demand updates. Our approach achieves near-optimal results for small instances and higher objective values as an alternative heuristic for larger instances. With the full integration of channels, omni-channel retailers can realize a profit increase that mainly depends on the magnitude of substitution rates. We further show numerically that in-channel substitution has a stronger impact on profits than cross-channel substitution when costs are equal across channels.

Package express companies routinely operate multiple equipment types in their service networks. Nevertheless, the weekly schedule of movements used to transport packages through the network leads to changes in equipment inventory at the facility level, which will hinder their normal operations if it is not carefully taken care of. Traditional rebalancing seeks to move the equipment empty in the most cost efficient way. In contrast, we investigate a substitution-based equipment balancing which has been rarely considered. More specifically, we try to reduce this change, i.e., the equipment imbalance associated with the schedule of movements, by substituting the equipment types initially assigned to movements. Consequently, substantial unnecessary empty repositioning needed to restore balance can be avoided at the end. We conduct complexity analysis of the underlying optimization problems, i.e., finding the minimum imbalance of the network and minimizing the number of substitutions required to achieve the minimum network imbalance. In addition, we develop integer programming (IP) models and propose an efficient two-phase decomposition heuristic for solution. Furthermore, we perform a computational study using real-world instances to analyze the performance of the IP solution approach and assess the benefits of substitution-based equipment balancing.

In this study, a distributed hybrid flow shop scheduling problem with variable speed constraints is considered. To solve it, a knowledge-based adaptive reference points multi-objective algorithm (KMOEA) is developed. In the proposed algorithm, each solution is represented with a three-dimensional vector, where the factory assignment, machine assignment, operation scheduling and speed setting are encoded. Then, four problem-specific lemmas are proposed, which are used as the knowledge to guide the main components of the algorithm, including the initialization, global and local search procedures. Next, an efficient initialization approach is presented, which embedded with several problem-related initialization rules. Furthermore, a novel Pareto-based crossover heuristic is designed to learn from more promising solutions. To enhance the local search abilities, a speed adjustment local search method is investigated. Finally, a set of instances generated based on the realistic prefabricated production system is tested to verify the efficiency and effectiveness of the proposed algorithm.

In this study, we present a flexible delivery routing problem faced by logistics service providers in which some customers may receive their packages indirectly. Customers are supposed to get their packages directly from a delivery service provider or be delivered to indirectly using a nearby station drop and a subsequent separate last-mile delivery service provider that finally delivers their goods. We address the problem of determining whether deliveries to customers should be fulfilled directly or indirectly in this situation. We present the mathematical programming model and propose a near-optimal heuristic approach based on a memetic algorithm. In addition, we evaluate the numerical performance of the proposed algorithm and perform various parametric analyses to gain managerial insights from the model.