یک روش برنامه ریزی محدود برای طراحی یک سیستم توزیع روزنامه

This paper presents a constraint programming approach using a modeling language and CP optimizer to aid in the coordination of the production and delivery of multi-product newspapers to bulk delivery locations. The distribution problem is modeled as an open vehicle routing problem with time windows and zoning constraints. The use of a high level modeling language eliminates the need to develop custom low-level computer codes to solve the problem. The methodology is applied to the newspaper production and distribution problem in a major metropolitan area. Computational results are presented and show significant improvement relative to a previous metaheuristic approach using tabu search.

In this paper we present a constraint programming and optimization approach to integrate and coordinate the production and distribution of newspapers for a mid-sized newspaper publisher. The proposed methodology achieves consistently superior results compared to previous work involving a two-phase approach and a tabu search metaheuristic. The newspaper industry needs to reduce logistics and operating costs more than ever because of intense competition from the Internet and in many instances, shrinking advertising revenue. Aside from the human resources and the materials utilized on a daily basis in producing newspapers, the physical distribution of the newspaper product is the highest day-to-day operational cost associated with the newspaper publishing business. The distribution of the daily newspaper is becoming more and more of a concern because of the growth rate experienced in the pre-print segment of newspaper advertising and the need to provide subscribers with reliable delivery service. Pre-Print advertising has now become an integral part of the newspaper. In many instances, pre-print advertising is the preferred method of advertising for many large volume advertisers because of the different attributes available in a pre-print product. Because of the various sizes, weights, zones, distribution dates, and other variables, there is an incremental cost associated with handling the growing pre-print advertising products. Newspaper companies, such as The Tulsa World, have a need to more effectively integrate the production, loading, and distribution of the newspaper and its associated advertising products. The complexity is no longer simply related to technology and equipment, but goes further in having the ability to adapt the newspaper’s processes in production and distribution with the aid of logistics information to provide a more flexible, efficient, and customer-oriented operation. Successful newspapers understand that a core capability of their business is their distribution and logistics network and that it is necessary to identify where their performance can be improved in order to continue to be successful. Over the years, as the pre-print advertising segment outgrew the manual capacity of packaging the various parts of the newspaper, investments in on-line inserting equipment were the trend with the pre-print advertising material being inserted into the newspaper as it was being produced. As the pre-print market continued to grow, many newspaper companies outgrew the efficiency of on-line inserting and changed their packaging deadlines in order to create pre-print packages a day or more before the distribution. The Tulsa World, as well as many other large newspaper companies, is now distributed in multiple packages containing the actual newspaper and the pre-print advertising material. Because of the timing involved in the production of the newspaper, various editions and parts are produced with different content for a specific geographic zone creating a targeted advertising product. In comparison to the printing of the newspaper itself, the pre-print advertising material is delivered to a processing warehouse from a few days to a few weeks in advance of the packaging deadline. The pre-print materials are fed into an inserting machine to create zoned advertising packages based on the advertisers’ geographic requirements. The packages are counted, stacked, labeled for zoning, tied in bundles, and are picked up just prior to the loading of the newspaper packages. (This is another example of product differentiation postponement in supply chains). The delivery drivers are required to handle multiple packages with certain variations. The larger that the newspaper and the pre-print packages are, the larger the vehicle for transportation needs to be, and longer lead times are necessary for distribution. Web based advertising continues to pose a formidable threat to newspapers and other media sources. As internet advertising revenues reach all time highs, massive changes in the world of advertising are expected. With more and more advertisers pushing for better targeting or zoning capabilities, The Tulsa World has been trying to creatively provide advertisers with solutions. Therefore, it is compelled to solve the problem as to how to manage the zoning of the growing pre-print advertising products more efficiently and cost effectively in order to remain competitive. Chandra and Fisher (1994) conducted a computational study to investigate the value of coordinating production and distribution planning by comparing two approaches. In the first approach the production scheduling and vehicle routing problems are solved separately; in the second approach they are coordinated within a single model. They conclude that the reduction in total operating cost from coordination ranged from 3 to 20%. Their work is relevant to our investigation of newspaper logistics in that they considered the integration of production scheduling and vehicle routing. Other approaches reported in the literature pertaining to the coordination or integration of logistics or supply chain activities has ranged from heuristics and metaheuristics to various types of optimization. Cohen and Lee (1988) studied the impact of various materials management strategies on the cost of production and service levels. Their work integrates the supply chain in terms of inventory distribution without considering their impact on physical distribution strategies. Ishii et al. (1988) tried to determine economic levels for the base stock and lead times for production and transportation in integrated production and distribution systems based on the pull type ordering system. Pyke and Cohen (1994) presented a model to represent an integrated production–distribution system comprised of a single station model of a factory, a stockpile of finished goods, and a single retailer and provide a near-optimization algorithm to solve the problem. Viswanathan and Mathur (1997) present a heuristic to determine replenishment policies that specify the delivery quantities and the vehicle routes to minimize the long-run average inventory and transportation costs for distribution systems with a central warehouse and many retailers that stock a number of different products. Carter and Ragsdale (2002) look at the pre-print advertising scheduling problem using a genetic algorithm (GA) approach. Their computational results using data from a mid-size newspaper show that the GA approach to developing schedules reduces the processing time associated with creating the pre-print packages. Van Buer et al. (1999) solved a medium newspaper production/distribution problem with various heuristic search algorithms and found that re-using trucks that have completed earlier routes is one way to achieve low-cost solutions. Russell et al. (2008) used a two-phase approach to the newspaper distribution problem. A generalized assignment problem was used to assign vehicle routes to clusters in order to satisfy a zone requirement that no route will cover more than two advertising zones. A tabu search metaheuristic was then employed to improve the routes. The two-phase approach achieved significant improvements in route efficiency compared to the existing distribution system. In a subsequent simulation study, Chiang et al. (2009) examined the stochastic aspects of the newspaper production and distribution system and were able to achieve a higher level of customer service in terms of on-time delivery. In this paper we approach the synchronization and coordination of newspaper production and delivery using a novel constraint programming formulation of the open vehicle routing problem adapted to the specific requirements of newspaper distribution.

In this paper we have developed a constraint programming model to effectively plan the distribution of newspapers from plant to bulk delivery locations. The model provides a means to reduce both the number of vehicles and the total distance traveled to better meet the challenges of the marketplace. Improved distribution routes will provide the newspaper the freedom to develop new targeted advertising products while maintaining operational efficiency to maximize the productivity and profitability of the newspaper packaging and distribution functions. In our approach to the problem, the key problem characteristics include zone constraints, time windows, multiple products, and diminishing time horizons as a function of vehicle route start times. It is the multiplicity of constraints that partially explains the success of constraint programming on the newspaper logistics problem. As more constraints exist, it is more difficult for metaheuristic approaches to satisfy all constraints while searching for feasible and improved solutions. Another explanation for the success of constraint programming and CP Optimizer is the fact that the model encompasses the entire problem. The tabu search metaheuristic, while effective, requires a 2-stage approach in which capacity and zone constraints are satisfied in phase 1 and route improvements are made in phase 2. Such a hierarchical approach leaves room for improvement through the simultaneous solution of the entire problem. The computational requirements are significantly more than that required by the tabu search metaheuristic, but are well within 1 h of CPU time on a modern personal computer. These results were obtained on problems ranging from 77 to 106 total locations. Furthermore, the constraint programming model is developed within a high level modeling language and eliminates the need to develop custom lower level computer codes for the problem’s solution. The newspaper’s shelf life is a single morning and therefore any delay could result in the loss of customer satisfaction and sales. By realizing time savings in logistics and delivery while meeting the capacity and time constraints, the newspaper company can better manage the production and distribution deadlines as well as the frequent overloading of delivery routes. As the pre-print volume increases and gets more complex, a systematic approach to optimize the delivery routes will allow the newspaper to offer the advertisers more precise zoning options. The proposed methodology also provides the newspaper a way to more efficiently utilize the fleet’s assets to reduce operational inefficiencies which are the root of many customer service related issues. The newspaper company can take advantage of a systematic delivery approach to better meet the advertiser’s and the subscriber’s expectations of delivering the product reliably and on time.