We examine a routing problem that arises when an unmanned aerial vehicle (UAV), or drone, is used in the last-stretch of parcel delivery to end customers. In the scenario that we study, a delivery truck is dispatched carrying a shipment of parcels to be delivered to customers. While the truck is following a predetermined route, a drone is charged with making the last-stretch delivery of a parcel from the truck to a customer's doorstep. Given a set of customers to be served and a set of rendezvous points where the drone can meet with the truck to pick up a parcel, we ask what the quickest way is of delivering all parcels to the end customers. We model this problem as a problem of finding a special type of a path in a graph of a special structure, and show that the graph problem is NP-hard even when all edge weights are restricted to be 1 or 2. Furthermore, we identify a special instance type that can be solved optimally in polynomial time. Finally, we propose a polynomial-time approximation algorithm for the graph problem in metric graphs, and show that its approximation ratio is bounded above by 2 in restricted metric graphs.
Inference of chemical compounds with desired properties is important for drug design, chemo-informatics, and bioinformatics, to which various algorithmic and machine learning techniques have been applied. Recently, a novel method has been proposed for this inference problem using both artificial neural networks (ANN) and mixed integer linear programming (MILP). This method consists of the training phase and the inverse prediction phase. In the training phase, an ANN is trained so that the output of the ANN takes a value nearly equal to a given chemical property for each sample. In the inverse prediction phase, a chemical structure is inferred using MILP and enumeration so that the structure can have a desired output value for the trained ANN. However, the framework has been applied only to the case of acyclic and monocyclic chemical compounds so far. In this paper, we significantly extend the framework and present a new method for the inference problem for rank-2 chemical compounds (chemical graphs with cycle index 2). The results of computational experiments using such chemical properties as octanol/water partition coefficient, melting point, and boiling point suggest that the proposed method is much more useful than the previous method.
14 September 2021 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Drug discovery is one of the major goals of computational biology and bioinformatics. A novel framework has recently been proposed for the design of chemical graphs using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase. In the first phase, an ANN is trained using data on existing chemical compounds. In the second phase, given a target chemical property, a feature vector is inferred by solving an MILP formulated from the trained ANN and then a set of chemical structures is enumerated by a graph enumeration algorithm. Although exact solutions are guaranteed by this framework, the types of chemical graphs have been restricted to such classes as trees, monocyclic graphs and graphs with a specified polymer topology with cycle index up to 2. To overcome the limitation on the topological structure, we propose a new flexible modeling method to the framework so that we can specify a topological substructure of graphs and a partial assignment of chemical elements and bond-multiplicity to a target graph. The results of computational experiments suggest that the proposed system can infer chemical graphs with around up to 50 non-hydrogen atoms.