Shipper collaboration

The interest in collaborative logistics is fuelled by the ever increasing pressure on companies to operate more efficiently, the realization that suppliers, consumers, and even competitors, can be potential collaborative partners in logistics, and the connectivity provided by the Internet. Logistics exchanges or collaborative logistics networks use the internet as a common computing platform to implement strategies designed to reduce “hidden costs” such as asset reposition costs. Through collaboration shippers may be able to identify and submit tours with little or no asset repositioning to a carrier, as opposed to submitting individual lanes, in return for more favorable rates. In this paper, we focus on finding a set of tours connecting regularly executed truckload shipments so as to minimize asset repositioning. Mathematically, the truckload shipper collaboration problem translates into covering a subset of arcs in a directed Euclidean graph by a minimum cost set of constrained cycles. We formulate the lane covering problem, propose several solution algorithms, and conduct a computational study on the effectiveness of these methodologies.     

A Sampling-Based Stochastic Winner Determination Model for Truckload Service Procurement

Many large shippers procure truckload (TL) service from carriers via a combinatorial auction. In order to determine the winners of the auction, they need to solve a combinatorial optimization problem known as winner determination problem (WDP). In practice, shippers must resolve the WDP under shipment volume uncertainty due to limited information of future demands. In this paper, we propose a sampling-based two-stage stochastic programming approach to solve WDP under shipment volume uncertainty. We propose a refined formulation of deterministic WDPs in which shortage in shipments and the associated penalty cost are explicitly modeled. We demonstrate that the refined model is more general and more feasible under uncertainty than the benchmarks. Theoretical results pertaining to problem feasibility are derived and their insights to TL service procurement are provided. We propose a sampling-based solution approach called Monte Carlo Approximation (MCA) and use numerical tests to show that MCA is numerically tractable for solving moderately sized instances of TL service procurement. Finally, we verify via Monte Carlo simulation that the solution to our proposed stochastic WDP yields lower procurement cost than the solution to the deterministic WDP.     

Privacy-preserving collaborative recommendations based on random perturbations

Collaborative recommender systems offer a solution to the information overload problem found in online environments such as e-commerce. The use of collaborative filtering, the most widely used recommendation method, gives rise to potential privacy issues. In addition, the user ratings utilized in collaborative filtering systems to recommend products or services must be protected. The purpose of this research is to provide a solution to the privacy concerns of collaborative filtering users, while maintaining high accuracy of recommendations. This paper proposes a multi-level privacy-preserving method for collaborative filtering systems by perturbing each rating before it is submitted to the server. The perturbation method is based on multiple levels and different ranges of random values for each level. Before the submission of each rating, the privacy level and the perturbation range are selected randomly from a fixed range of privacy levels. The proposed privacy method has been experimentally evaluated with the results showing that with a small decrease of utility, user privacy can be protected, while the proposed approach offers practical and effective results.     

铁路快捷货物货源组织优化模型及算法

针对铁路快捷货物货主在选择货运产品时具有越来越多的主动权,研究货主选择车次条件下的快捷货物货源组织优化问题。构建了以货源组织成本最小为目标的0-1规划模型,并根据问题的特点,设计了整数编码的遗传算法进行求解。通过一个数值算例对模型和算法的可行性及有效性进行了验证。研究结果表明,所提出的方法能够综合反映铁路和货主双方的收益,可为铁路货运组织改革条件下的快捷货物货源组织提供参考。     

输出图的全部Hamiltonian回路的新算法

为求出图的全部哈密顿回路,本文提出了H集合、连接积、H矩阵和通路矩阵等概念。给出了基于这些概念下的一些哈密顿回路的存在性判定定理和通过构造通路矩阵序列Mk=Mk-1*M(k=2,...,n)的办法输出简单图（无向或有向）的全部哈密顿回路的算法和实例。本算法特别适合寻找图的最短哈密顿回路,较其它算法更为简单直观。     

Routing electric meter readers

Electric utility companies employ a crew of workers who periodically visit and read the electric meters of each customer in their service area. Each reader is transported by auto from a central office to the first customer on his work list. At the end of his work shift time limit the reader is free to leave the area possibly returning home or to the central office by public bus. Taking a graph that corresponds to the city network of streets meter readers must traverse each street while moving from house to house. It is possible that dead heading may be required—back tracking over a street that has already been covered. A working tour is an open path whose reading time plus deadheading time does not exceed the work limit. The problem is to find the minimum number of working tours. Stating the problem in this manner gives us an optimization problem closely related to the M-Chinese postman problem—an edge oriented routing problem. After presenting some background on this type of problem a heuristic procedure is used to solve an example from the City of Beersheva. The solution provides a 40% reduction in the number of working tours. The paper ends with a discussion of the solution, and provides conditions under which the algorithm should have practical utility.     

Using and determining location in a context-sensitive tour guide

In a study that provided unique insights into the challenges associated with developing location-based applications, the Lancaster Guide project used members of the general public to test a network-centric electronic tourist guide. We discuss two main topics. The first is our choice of positioning technology - beacons that broadcast using an IEEE 802.11 wireless network combined with user input. The second topic concerns techniques for generating custom tours for electronic city-guide systems. Guide generates these custom tours by taking into account multiple contextual triggers and user preferences. In practice, producing good tours and, indeed, assessing the quality of a tour are difficult tasks. While our analysis of techniques for producing custom tours is somewhat specific to the city-guide domain we believe that the majority of our work is relevant to location-based systems in general     

Truck driver scheduling in Australia

In September 2008 new regulations for managing heavy vehicle driver fatigue entered into force in Australia. According to the new regulations there is a chain of responsibility ranging from drivers to dispatchers and shippers and thus, carriers must explicitly consider driving and working hour regulations when generating truck driver schedules. This paper presents and studies the Australian Truck Driver Scheduling Problem (AUS-TDSP) which is the problem of determining whether a sequence of locations can be visited within given time windows in such a way that driving and working activities of truck drivers comply with Australian Heavy Vehicle Driver Fatigue Law.     

Solving a rich vehicle routing and inventory problem using column generation

The livestock collection problem (LCP) is a rich vehicle routing problem (VRP) extended with inventory constraints. The LCP is a complex planning problem taken from the meat industry, and the goal is to construct a set of vehicle routes to collect animals from farms for slaughter at a slaughterhouse. Several constraints dealing with animal welfare are added, some of these lead to a loading problem where the vehicle capacity depends on the loading sequence. In addition, global constraints to handle production and inventory at the slaughterhouse are needed. This paper presents an exact solution method for the LCP, based on column generation, that solves much larger instances to optimality than what has been done before. The algorithm presented here also solves a richer model that is closer to the underlying real-world problem than previously published work on exact methods for this problem is based on.     

Capacitated lot-sizing and scheduling with sequence-dependent,period-overlapping and non-triangular setups

In production planning, sequence dependent setup times and costs are often incurred for switchovers from one product to another. When setup times and costs do not respect the triangular inequality, a situation may occur where the optimal solution includes more than one batch of the same product in a single period—in other words, at least one sub tour exists in the production sequence of that period. By allowing setup crossovers, flexibility is increased and better solutions can be found. In tight capacity conditions, or whenever setup times are significant, setup crossovers are needed to assure feasibility. We present the first linear mixed-integer programming extension for the capacitated lot-sizing and scheduling problem incorporating all the necessary features of sequence sub tours and setup crossovers. This formulation is more efficient than other well known lot-sizing and scheduling models.     

A computational analysis of LCP methods for bilinear and concave quadratic programming

The use of a sequential linear complementarity problem (SLCP) algorithm for finding a global minimum of bilinear programming problem (BLP) or a concave quadratic program (CQP) is examined. The algorithm consists of solving a sequence of linear complementarity problems (LCP). A branch-and-bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into an LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient in finding a global minimum (or at least a solution that is quite near the optimum), but it is, in general, unable to establish that such a solution has been found. An algorithm to find a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the branch-and-bound method and another alternative technique.     

A plug-based microfluidic system for dispensing lipidic cubic phase (LCP) material validated by crystallizing membrane proteins in lipidic mesophases

This article presents a plug-based microfluidic system to dispense nanoliter-volume plugs of lipidic cubic phase (LCP) material and subsequently merge the LCP plugs with aqueous plugs. This system was validated by crystallizing membrane proteins in lipidic mesophases, including LCP. This system allows for accurate dispensing of LCP material in nanoliter volumes, prevents inadvertent phase transitions that may occur due to dehydration by enclosing LCP in plugs, and is compatible with the traditional method of forming LCP material using a membrane protein sample, as shown by the successful crystallization of bacteriorhodopsin from Halobacterium salinarum. Conditions for the formation of LCP plugs were characterized and presented in a phase diagram. This system was also implemented using two different methods of introducing the membrane protein: (1) the traditional method of generating the LCP material using a membrane protein sample and (2) post LCP-formation incorporation (PLI), which involves making LCP material without protein, adding the membrane protein sample externally to the LCP material, and allowing the protein to diffuse into the LCP material or into other lipidic mesophases that may result from phase transitions. Crystals of bacterial photosynthetic reaction centers from Rhodobacter sphaeroides and Blastochloris viridis were obtained using PLI. The plug-based, LCP-assisted microfluidic system, combined with the PLI method for introducing membrane protein into LCP, should be useful for minimizing consumption of samples and broadening the screening of parameter space in membrane protein crystallization.     

Real-time collaboration through web applications: an introduction to the Toolkit for Web-based Interactive Collaborative Environments (TWICE)

The widespread availability of personal mobile devices, combined with the increasing availability of stationary public devices such as large interactive displays, creates new opportunities for computer-supported collaborative work. In particular, these two factors enable the emergence of collaborative scenarios, whether planned or spontaneous, in any location, and previous obstacles to such collaborative settings such as limitations on the number of devices available for use and infrastructure costs can be overcome more easily. As hardware restrictions diminish, the need for software toolkits that simplify the development of distributed collaborative applications allowing for device heterogeneity, true multi-user interaction and spontaneous emergence increases. In this article, we describe the Toolkit for Web-based Interactive Collaborative Environments whose aim is to address these issues. This is done using current standard web technologies extended for real-time application (and structured using specific development guidelines) while ensuring compatibility with the manifold new evolutions in the currently ongoing development of open web platform (HTML5, websockets, etc). While our own work has mainly focused on synchronous co-located collaborative systems (same place/same time), our solution, the technologies used, as well as the concepts that are introduced are easily extendable for remote and/or asynchronous collaboration.     

A Game Theoretical Approach for Improving the Operational Efficiencies of Less-than-truckload Carriers Through Load Exchanges

Less-than-truckload (LTL) transportation offers fast, flexible and relatively low-cost transportation services to shippers. In order to cope with the effects of economic recessions, the LTL industry implemented ideas such as reducing excess capacity and increasing revenues through better yield management. In this paper, we extend these initiatives beyond the reach of individual carriers and propose a collaborative framework that facilitates load exchanges to reduce the operational costs. Even though collective solutions are proven to provide benefits to the participants by reducing the inefficiencies using a system-wide perspective, such solutions are often not attainable in real-life as the negotiating parties are seeking to maximize their individual profits rather than the overall profit and also they are unwilling to share confidential information. Therefore, a mechanism that enables collaboration among the carriers should account for the rationality of the individual participants and should require minimal information transfer between participants. Having this in mind, we propose a mechanism that facilities collaboration through a series of load exchange iterations and identifies an equilibrium among selfish carriers with limited information transfer among the participants. Our time-efficient mechanism can handle large instances with thousands of loads as well as provide significant benefits over the non-collaborative management of LTL networks.

     

Distributed constraint optimization with MULBS: A case study on collaborative meeting scheduling

This paper introduces MULBS, a new DCOP (distributed constraint optimization problem) algorithm and also presents a DCOP formulation for scheduling of distributed meetings in collaborative environments. Scheduling in CSCWD can be seen as a DCOP where variables represent time slots and values are resources of a production system (machines, raw-materials, hardware components, etc.) or management system (meetings, project tasks, human resources, money, etc). Therefore, a DCOP algorithm must find a set of variable assignments that maximize an objective function taking constraints into account. However, it is well known that such problems are NP-complete and that more research must be done to obtain feasible and reliable computational approaches. Thus, DCOP emerges as a very promising technique: the search space is decomposed into smaller spaces and agents solve local problems, collaborating in order to achieve a global solution. We show with empirical experiments that MULBS outperforms some of the state-of-the-art algorithms for DCOP, guaranteeing high quality solutions using less computational resources for the distributed meeting scheduling task.     

mStar: enabling collaborative applications on the Internet

Distributed, real-time multimedia applications on the Internet permit users to cooperate in new and more interesting ways for collaborative teamwork and net-based learning. The mStar environment features an agent-based architecture, implemented in Java, which preserves compatibility with the dominant Mbone paradigm for IP multicast. The shared software environment provides an integrated solution for generating, presenting, scoring, and editing media in collaborative applications. In particular, mStar supports developers in creating distributed, real-time multimedia software applications such as e-meetings. mStar enhances both distance education and collaborative teamwork by presenting a uniform user interface for real-time audio and video, shared whiteboard, char, voting, and distributed Web-based presentations. The system also supports on-demand recording and session playback     

A search algorithm for the traveling salesman problem

A search algorithm, based on the concepts of lexicographic search and sequential decision processes, is proposed for the solution of the traveling salesman problem. Starting with an initial trial solution, the search algorithm sequentially generates better tours until an optimal (least cost) tour is identified. The logical structure of the search algorithm is such that the computational effort required to solve a problem by the proposed approach is less than that by the branch and bound procedures.     

Two memetic algorithms for heterogeneous fleet vehicle routing problems

The vehicle routing problem (VRP) plays an important role in the distribution step of supply chains. From a depot with identical vehicles of limited capacity, it consists in determining a set of vehicle trips of minimum total length, to satisfy the demands of a set of customers. In general, the number of vehicles used is a decision variable. The heterogeneous fleet VRP (HFVRP or HVRP) is a natural generalization with several vehicle types, each type being defined by a capacity, a fixed cost, a cost per distance unit and a number of vehicles available. The vehicle fleet mix problem (VFMP) is a variant with an unlimited number of vehicles per type. This paper presents two memetic algorithms (genetic algorithms hybridized with a local search) able to solve both the VFMP and the HVRP. They are based on chromosomes encoded as giant tours, without trip delimiters, and on an optimal evaluation procedure which splits these tours into feasible trips and assigns vehicles to them. The second algorithm uses a distance measure in solution space to diversify the search. Numerical tests on standard VFMP and HFVRP instances show that the two methods, especially the one with distance measure, compete with published metaheuristics and improve several best-known solutions.     

The influence of virtual tour on urban visitor using a network approach

Virtual tours provide an interactive experience for potential visitors, influencing the destination image and the intention to visit. However, virtual tours are limited to one-way communication, and there is a need to quantitatively analyze the influence of virtual tours based on the context of physical movement. Therefore, this study aimed to quantitatively analyze the virtual influence from a network perspective and to analyze changes in destination image and intention to visit through a two-way virtual tour. We noted that virtual tours are confirmed to improve destination image and intention to visit, and the experience of a place in Minecraft plays a mediator role in the activation of local visits. This study demonstrates that virtual tours can be a mediator to help local visits and that virtual tours affect physically marginalized. We believe these findings can be applied as practical solutions for areas with physical mobility constraints and contribute to urban visitor studies.     

A GRASP×ELS approach for the capacitated location-routing problem

This paper addresses the capacitated location-routing problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The CLRP is defined by a set of potential depot locations, with opening costs and limited capacities, a homogeneous fleet of vehicles, and a set of customers with known demands. The objective is to open a subset of depots, to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed solution method is a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS) and searching within two solution spaces: giant tours without trip delimiters and true CLRP solutions. Giant tours are evaluated via a splitting procedure that minimizes the total cost subject to vehicle capacity, fleet size and depot capacities. This framework is benchmarked on classical instances. Numerical experiments show that the approach outperforms all previously published methods and provides numerous new best solutions.